第三十章 数论——扩展中国剩余定理
第三十章 数论——扩展中国剩余定理
- 一、中国剩余定理的弊端
- 二、扩展中国剩余定理
- 1、作用
- 2、内容
- 3、问题
- 4、代码
一、中国剩余定理的弊端
在第二十九章中，作者详细地讲解了中国剩余定理的使用，在开始本章节的讲解之前，建议读者先去看上一章节的讲解。传送门：中国剩余定理与线性同余方程组
中国剩余定理是用来解决线性同余方程组的，但是有一个很苛刻的要求就是：方程组中的同余方程的模数必须是互质的。只有这样我们才能套用中国剩余定理。
二、扩展中国剩余定理
1、作用
扩展中国剩余定理就是为了解决方程组中模数不互质的情况。
2、内容
{x≡a1mod(m1)x≡a2mod(m2)x≡a3mod(m3)...x≡anmod(mn)\begin{cases} x\equiv a_1\ mod(m_1)\\ x\equiv a_2\ mod(m_2)\\ x\equiv a_3\ mod(m_3)\\ ...\\ x\equiv a_n\ mod(m_n) \end{cases} ⎩⎨⎧x≡a1 mod(m1)x≡a2 mod(m2)x≡a3 mod(m3)...x≡an mod(mn)
我们取出前两个式子：
x≡a1mod(m1)x≡a2mod(m2)x\equiv a_1\ mod(m_1)\\ x\equiv a_2\ mod(m_2)\\ x≡a1 mod(m1)x≡a2 mod(m2)
这两个式子能够写成：
x=k1m1+a1x=k2m2+a2x=k_1m_1+a_1\\ x=k_2m_2+a_2 x=k1m1+a1x=k2m2+a2
两个式子相减：
k1m1+a1=k2m2+a2k_1m_1+a_1=k_2m_2+a_2k1m1+a1=k2m2+a2
将上面的式子移项：
k1m1−k2m2=a2−a1k_1m_1-k_2m_2=a_2-a_1k1m1−k2m2=a2−a1
我们把k1k_1k1和−k2-k_2−k2看作xkx_kxk和yky_kyk。
那么这个式子就可以写成：
xkm1+ykm2=(a2−a1)x_km_1+y_km_2=(a_2-a_1)xkm1+ykm2=(a2−a1)
根据我们的裴蜀定理：
如果gcd(m1,m2)∣(a2−a1)gcd(m_1,m_2)|(a_2-a_1)gcd(m1,m2)∣(a2−a1)
我们就能够根据扩展欧几里德算法计算出系数。
如果上述整除的关系不成立，说明这个式子是无解的。
我们现在来讨论整除关系成立的情况：
我们可以根据欧几里得算法计算出：
x0m1+y0m2=gcd(m1,m2)x_0m_1+y_0m_2=gcd(m1,m2)x0m1+y0m2=gcd(m1,m2)的特殊解。
为了得到我们的xkx_kxk和yky_kyk，我们需要给两遍同乘(a2−a1)gcd(m1,m2)\frac{(a_2-a_1)}{gcd(m_1,m_2)}gcd(m1,m2)(a2−a1)
所以我们的xxx和yyy的特殊解可以写成：
xk1=x0∗(a2−a1)gcd(m1,m2)yk1=y0∗(a2−a1)gcd(m1,m2)x_{k1}=x_0*\frac{(a_2-a_1)}{gcd(m_1,m_2)}\\ y_{k1}=y_0*\frac{(a_2-a_1)}{gcd(m_1,m_2)}xk1=x0∗gcd(m1,m2)(a2−a1)yk1=y0∗gcd(m1,m2)(a2−a1)
但是这是一组特殊解：
当我们式子为：
x0m1+y0m2=n∗gcd(m1,m2)x_0m_1+y_0m_2=n*gcd(m1,m2)x0m1+y0m2=n∗gcd(m1,m2)
此时我们可以通过特殊解构造出一般解：
我们构造的原则是下面的等式恒成立：
x0m1+y0m2=gcd(m1,m2)x_0m_1+y_0m_2=gcd(m1,m2)x0m1+y0m2=gcd(m1,m2)
因此我们给我们的特殊解进行如下变形：
xk=xk1+m2gcd(m1,m2)∗nyk=yk1−m1gcd(m1,m2)∗nx_k=x_{k1}+\frac{m_2}{gcd(m_1,m_2)}*n\\ y_k=y_{k1}-\frac{m_1}{gcd(m_1,m_2)}*nxk=xk1+gcd(m1,m2)m2∗nyk=yk1−gcd(m1,m2)m1∗n
我们将这两个式子带回：x0m1+y0m2=gcd(m1,m2)x_0m_1+y_0m_2=gcd(m1,m2)x0m1+y0m2=gcd(m1,m2)
发现依然是成立的。
所以我们构造的xkx_{k}xk和yky_{k}yk就是通解。
此时带回我们的
x=k1m1+a1x=k_1m_1+a_1x=k1m1+a1
我们前面是将k1k_1k1看作了xkx_kxk，所以我们的式子可以变形为：
x=m2∗m1gcd(m1,m2)∗n+xk1∗m1+a1x=\frac{m_2*m_1}{gcd(m_1,m_2)}*n+x_{k1}*m_1+a_1x=gcd(m1,m2)m2∗m1∗n+xk1∗m1+a1
而m2∗m1gcd(m1,m2)\frac{m_2*m_1}{gcd(m_1,m_2)}gcd(m1,m2)m2∗m1就是我们的最小公倍数。因为：
最大公因数∗最小公倍数=两个数的乘积最大公因数*最小公倍数=两个数的乘积最大公因数∗最小公倍数=两个数的乘积
所以我们让：
lcm(m1,m2)=m2∗m1gcd(m1,m2)lcm(m_1,m_2)=\frac{m_2*m_1}{gcd(m_1,m_2)}lcm(m1,m2)=gcd(m1,m2)m2∗m1
所以我们的式子可以化简为：
x=lcm(m1,m2)∗n+xk1m1+a1x=lcm(m_1,m_2)*n+x_{k1}m_1+a_1x=lcm(m1,m2)∗n+xk1m1+a1
而这个式子可以写成：
x≡r(modm)x\equiv r(mod\ m)x≡r(mod m)
其中：
{r=k1m1+a1m=lcm(m1,m2)\begin{cases} r={k_1}m_1+a_1\\ m=lcm(m_1,m_2) \end{cases} {r=k1m1+a1m=lcm(m1,m2)
经过上述推导，我们将两个同余方程：
x=k1m1+a1x=k2m2+a2x=k_1m_1+a_1\\ x=k_2m_2+a_2 x=k1m1+a1x=k2m2+a2
合并成了一个同余方程：
x≡r(modm)x\equiv r(mod\ m)x≡r(mod m)
因此，我们只需要不断地去合并，经过n−1n-1n−1次合并，我们就能够把nnn个同余方程合并成一个同余方程。
当只有一个合并方程的时候，我们肯定就能够利用扩展欧几里得算法进行计算了。
3、问题
4、代码
#include
#include
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y)
{if (!b){x = 1, y = 0;return a;}LL d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}
int main()
{int n;cin >> n;LL x = 0, m1, a1;cin >> m1 >> a1;for (int i = 0; i < n - 1; i ++ ){LL m2, a2;cin >> m2 >> a2;LL k1, k2;LL d = exgcd(m1, m2, k1, k2);if ((a2 - a1) % d){x = -1;break;}k1 *= (a2 - a1) / d;k1 = (k1 % (m2/d) + m2/d) % (m2/d);x = k1 * m1 + a1;LL m = abs(m1 / d * m2);a1 = k1 * m1 + a1;m1 = m;}if (x != -1) x = (a1 % m1 + m1) % m1;cout << x << endl;return 0;
}