数论 学习笔记

OI Wiki了解一下

最大公约数

1
2
3
4
int gcd(int a, int b){
if(b == 0) return a;
return gcd(b, a % b);
}

裴蜀定理(贝祖定理)

  • 设$a,b$是不全为零的整数,则存在整数$x,y$, 使得$ax+by=gcd(a,b)$.

扩展欧几里得

  • 用于求解方程$ax+by=gcd(a,b)$
  • 代码:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int exgcd(int a, int b, int &x, int &y){
    if(b == 0){
    y = 0, x = 1;
    return a;
    }
    int r = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return r;
    }

乘法逆元

如果一个线性同余方程$ax\equiv 1(mod\ b)$,则$x$称为$a\mod b$的逆元,记作$a^{-1}$。

$a^{-1}\cdot a \equiv 1(\mod n)$
例如:$3 \times 7\equiv 1(\mod 20)$

求解:$ab\equiv 1 (\mod n)$
转化为:$n|ab-1$
即:$nk=ab-1$
移项:$ab-nk=1$
即可用exgcd求解(已知$a,n$求$b,k$)

求解a的逆元

扩展欧几里得法

  • 扩展欧几里得法和求解线性同余方程是一个原理,在这里不展开解释。

    快速幂法

  • 因为$ax\equiv 1(mod\ b)$

    所以$ax\equiv a^{b-1}(mod\ b)$

    所以$x\equiv a^{b-2}(mod\ b)$

然后就可以用快速幂求了

线性求任意n个数的逆元

首先计算$n$个数的前缀积$s_i$,然后用快速幂法求$s_n$的逆元,记为$sv_n$。

因为$sv_n$是前$n$个数的积的逆元,所以这个数乘$a_i$,会和其逆元抵消,于是就得到了$a_1$到$a_{n-1}$的积逆元,记为$sv_{n-1}$。

然后就能计算出所有$sv_i$,$a_i$的逆元就可以由$s_{i-1}\times sv_i$求得。

时间复杂度:$O(n+log\ p)$

1
2
3
4
5
6
s[0] = 1;
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p;
sv[n] = qpow(s[n], p - 2);
// 当然这里也可以用 exgcd 来求逆元,视个人喜好而定.
for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p;
for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;

P.S.刚刚我做了两道例题,现在感觉。。。脑子一片浆糊。😭


中国剩余定理(孙子定理)

「物不知数」问题

有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

$$
\left
{
\begin{array}{ccc}
x &\equiv& a_1 \pmod{m_1}\\
x &\equiv& a_2 \pmod{m_2}\\
&\vdots&\\
x &\equiv& a_n \pmod{m_n}
\end{array}
\right.
$$

  • 求解方法:
    1. 设$M=\prod_{i=1}^{n}m_i$,并设$M_i=M/m_i$。
    2. 设$t_i=M_i^{-1}$为$M_i$模$m_i$的数论倒数。
    3. 方程组的通解形式在模$M$的意义下有唯一解$x=\sum_{i=1}^na_it_iM_i$

扩展中国剩余定理(exCRT)

  • 考虑模数不互质的情况。
  • 如果只有两个方程
  • 设它们为$x\equiv a_1\pmod{m_1}$和$x\equiv a_2\pmod{m_2}$
  • 转化为$x=m_1p+a_1=m_2q+a_2$,其中$p,q$为整数,则有$m_1p-m_2q=a_2-a_1$
  • 由于裴蜀定理,若该式求出一组解$(p,q)$,则原来方程组解为$x\equiv b\pmod{M}$,其中$b=m_1p+a_1$,$M=lcm(m_1,m_2)$。
  • 考虑多个方程:按照上述方法两两合并即可。

【模板】扩展中国剩余定理

屠龙勇士

高斯消元

列主元Gauss-Jordan消元法

$$
\left
{
\begin{array}{ccc}
3x+2y+z=10\\
2x+y+3z=21\\
x+3y+2z=9
\end{array}
\right.
$$

化简

$$
\left
{
\begin{array}{ccc}
x+\frac{2}{3}y+\frac{1}{3}z=\frac{20}{3}\\
2x+y+3z=21\\
x+3y+2z=9
\end{array}
\right.
$$

(1),(2)消元

$$
\left
{
\begin{array}{ccc}
x+\frac{2}{3}y+\frac{1}{3}z=\frac{20}{3}\\
2x+y+3z=21\\
x+3y+2z=9
\end{array}
\right.
->
\left {
\begin{array}{ccc}
-\frac{1}{3}y+\frac{7}{3}z=\frac{23}{3}\\
\frac{7}{3}y+\frac{5}{3}z=\frac{7}{3}
\end{array}
\right.
$$

原(2),(3)消元

$$
\left {
\begin{array}{ccc}
-\frac{1}{3}y+\frac{7}{3}z=\frac{23}{3}\\
\frac{7}{3}y+\frac{5}{3}z=\frac{7}{3}
\end{array}
\right.
->
\left {
-\frac{54}{21}y=\frac{66}{21}
\right.
$$
往回代即可

# 数论

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×