数论小知识总结.

数论小课堂开课了，孩子上课听不懂，多半是零基础；

在Forsaken和Google的帮助下，让我实现了从零到中国剩余定理，在这里记录一下；

要了解中国剩余定理，先要知道扩展欧几里得，之前又要了解欧几里得算法才能推导出扩展欧几里得，好不容易推导出扩展欧几里得，发现他还可以用来求逆元，那还说什么，赶紧把逆元也总结一波；

所以本文将从欧几里得开始，经过乘法逆元的小插曲，到最终的扩展中国定理；作为初学者，本文将从最基础记录我的学习过程，本文面向对象也是初学者，（dalao也不会来看，，，如果有幸被看到欢迎指导；

欧几里得算法

欧几里得算法是用来计算最大公约数（greatest common divisor）的一个算法，简称GCD；

古时候人们用辗转相减法求最大公因数，也就是设a > b（后文无特别说明皆为如此）, $gcd(a, b) == gcd(a - b, b)$，简单证明如下:

设$c = gcd(a, b)$，那么$c | a$, $c | b$, $a = d * c$, b = e * c$, $a - b = (d - e) * c$, 所以$c | (a - b)$;

同理，$gcd(a, b) == gcd(a - 2 * b, b)$;

那么我们升级到辗转相除法:

\[gcd(a, b) == gcd(b, a \quad mod \quad b) \]

当一个数变为0时，任何数乘以0都得0，而另一个数字的最大约数就为另一个数字，显然，此时另一个数字就为最大公约数；

代码实现：

1
2
3

int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}

用gcd求最小公倍数

a和b的最小公倍数（Least Common Multiple）求解： \[lcm(a, b) == (a * b) / gcd(a, b)\]

直观理解就是除去两个数的相同因子；

代码实现：

1
2
3

int lcm(int a, int b){
    return (a * b) / gcd(a, b);
}

裴蜀定理

在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性丢番图方程（称为裴蜀等式）：

\[ax + by = m\]

有解当且仅当m是d的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解x、y都称为裴蜀数，可用辗转相除法求得。摘自维基百科；

翻译一下就是当$gcd(a, b) | c$时，方程才有整数解；简单证明：若存在整数解gcd(a, b) | (ax + by)，那么gcd(a, b) | m；

那么当gcd(a, b) | m时是否必然有整数解呢？？让扩展欧几里得为我们解答并解出一组x, y;

拓展欧几里得算法

将问题简化为 \[ax + by = gcd(a, b)\] 因为gcd(a, b) == gcd(b, a % b); 我们可以得到$ bx' + (a mod b)y' = ax + by $; 如此递归下去，当$y'$系数为0时，我们得到$x'$的系数为gcd(a, b), 此时$x' == 1$, $(a \quad mod \quad b)y' == 0$, 此时$y' == 0$;

我们往回推导x和y，将a mod b表示为$a - ⌊ a / b ⌋ * b$

我们得到$a * y' + b * (x' - ⌊ a / b ⌋ * y') = ax + by$;

通过待定系数法， $x = y'$, $y = x' - ⌊ a / b ⌋ * y'$;

可得整数解x, y; 再乘以m / gcd(a, b)即可得原问题一组解；再次证明裴蜀定理的同时得到了答案；

代码实现：

int ex_gcd(int a, int b, int s, int &x, int &y){
    if(b == 0)
        return x = s / a, y = 0, a;
    int g = ex_gcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

中国剩余定理（孙子定理）

ex欧几里得面对ax ≡ b(mod m)时(当b变为1时你是不是想到了乘法逆元？？快来看) 转化为ax + my = b便可求解；而中国剩余定理时用于求解同余方程组的解，便将用到ec_gcd；

\[\begin{equation} \left \lbrace \begin{array} & x \equiv a_1 (mod \quad m_1) \\\\ x \equiv a_2 (mod \quad m_2) \end{array} \right . \end{equation} \]

等价于

\[ \begin{equation} \left \lbrace \begin{array} & x = a_1 + k_1 * m_1 & \\\\ x = a_2 + k_2 * m_2 & \end{array} \right . \end{equation} \]

联立求解后得

\[ a_1 + k_1 * m_1 = x = a_2 + k_2 * m_2 \]

我们先假设$gcd(m_1, m_2) == 1$ 我们可以用ex_gcd求得一组(k_1', k_2') 此时回代得x设为$x_0$；

得到所有整数解： \[ \begin{equation} \left \lbrace \begin{array} kk_1 = m_2 * t + k_1' & \\\\ k_2 = m_1 * t + k_2' & \end{array} \right . \end{equation} \]

代入原方程中：

\[ \begin{equation} \begin{array} xx = a_1 + (m_2 * t + k_1 ') * m_1 \\\\ a_1 + m_1 * m_2 *t + k_1 * m_1 \\\\ x_0 + m_1 * m_2 * t \end{array} \end{equation} \]

多项同余方程的话多次合并即可得$x \equiv x_0(mod \quad m_1 * m_2 ... * m_n)$

但当模数并非两两互质的时候呢？

##拓展中国剩余定理

首先，我们再使用ex_gcd时就要考虑能不能得到正整数解了；当能得到正整数解时，如何得到所有正整数解呢？

已知$a_1 | m_1 \qquad a_2 | m_2$, 我们取g = gcd(m_1, m_2);

\[ k_1 * (m_1 / g) - k_2 * (m_2 / g) = x = (a_2 - a_2) / g\]

此时$k_1, k_2$的系数又互质了

此时所有正整数解为： \[ \begin{equation} \left \lbrace \begin{array} k_1 = (m_2 / g) * t + k_1' & \\ k_2 = (m_1 / g) * t + k_2' & \end{array} \right . \end{equation} \]

代入解得 $x = x_0 + (m_1 * m_2 / g) * t$

也就是$x = x_0 + lcm(m_1, m_2) * t$

多项和也就为$x \equiv x_0(mod \quad lcm(m_1 , m_2 ... , m_n))$

代码实现：

int  ex_crt(int m[], int a[], int n){
    for(int i = 1; i < n; i++){
        int k, y;
        int p = ex_gcd(m[0], -m[i], a[i] - a[0], k, y);
        if(p < 0)p *= -1;
        if((a[0] - a[i]) % p)return false;
        m[i] /= p;
        k = ((a[0] - a[i]) / p * x % m[i] + m[i]) % m[i];
        a[0] = a[0] + k * m[0];
        m[0] = m[0] * m[i];
    }
    a[0] = (a[0] % m[0] + m[0]) % m[0];
    return a[0];
}

实践一波 HDU - 1573 还有poj - 1006 几乎裸题，看完上面就能做，就不附题解了；

附记

通解写完了，但孙子定理却不是这样做的；孙子定理是在模数互质的情况下， \[ \begin{equation} \left \lbrace \begin{array} xx \equiv a_1 (mod \quad m_1) & \\\\ x \equiv a_2 (mod \quad m_2) & \\\\ ... & \\\\ x \equiv a_n (mod \quad m_n) & \end{array} \right . \end{equation} \]

让每一个式子的解都能被其他式子的模整除，同时模自己的m[i]还要等于a[i]

我们设$M = m_1 * m_2 * m_3 ... * m_n$; 为了让x模$m_n$能够得到$a_i$，那么必然要让x与$a_i$相关联。首先我们知道$a_i \equiv a_i (mod \quad m_i)$, 设Mi = M / mi, 构造Mi%mi的逆元t，得到$Mi*t \equiv 1 (mod \quad m_i)$, 根据模运算的可乘性，得到$Mi * t * a_i \equiv a_i (mod \quad m_i)$, 再将所有解相加，即可得最终解；

代码实现：

ll crt(int n) {
 ll ans = 0, M = 1;
 for (int i = 1; i <= n; i++) {
 M *= m[i];
 }
 for (int i = 1; i <= n; i++) {
 ll tmp = M / m[i];
 ll x, y;
 ex_gcd(tmp, mr[i], x, y);
 ans = (ans + tmp * x * a[i]) % M;
 }
 return (ans % M + M) % M;
}

参考文章：http://blog.miskcoo.com/2014/09/chinese-remainder-theorem https://blog.csdn.net/dafang_xu/article/details/50818919

Prev Home Next

从零到中国剩余定理

欧几里得算法

用gcd求最小公倍数

裴蜀定理

拓展欧几里得算法

中国剩余定理（孙子定理）

附记

Comments