中国剩余定理算法的实现

我作为一个初中蒟蒻，听y大视频听了5遍还不懂，快哭了。然后终于（好像）搞懂，写成题解加深一下记忆…

1. 将式子等价转换
   对于每两个式子（我们考虑将其合并）：

x≡m1(% a1)x≡m1(% a1)
x≡m2(% a2)x≡m2(% a2)
则有：

x=k1∗a1+m1x=k1∗a1+m1
x=k2∗a2+m2x=k2∗a2+m2
进一步：

k1∗a1+m1=k2∗a2+m2k1∗a1+m1=k2∗a2+m2
移项：

k1∗a1−k2∗a2=m2−m1k1∗a1−k2∗a2=m2−m1
也就是：

① k1∗a1+k2∗(−a2)=m2−m1k1∗a1+k2∗(−a2)=m2−m1
也就是我们需要找到一个最小的k1,k2k1,k2，使得等式成立（因为要求xx最小，而aa和mm都是正数）。

2. 用扩展欧几里得算法找出一组解
   我们已知a1,m1,a2,m2a1,m1,a2,m2，可以用扩展欧几里得算法算出一个k′1,k′2k1′,k2′使得：

k′1∗a1+k′2∗(−a2)=gcd(a1,−a2)k1′∗a1+k2′∗(−a2)=gcd(a1,−a2)
无解判断：
若gcd(a1,−a2)∤m2−m1gcd(a1,−a2)∤m2−m1，则无解。

我们设d=gcd(a1,−a2),y=(m2−m1)dd=gcd(a1,−a2),y=(m2−m1)d
承接上文，我们只需让k1,k2k1,k2分别扩大yy倍，则可以找到一个k1,k2k1,k2满足①式：

k1=k′1∗y,k2=k′2∗yk1=k1′∗y,k2=k2′∗y
3. 找到最小正整数解
我们知道一个性质：

②k1=k1+k∗a2dk1=k1+k∗a2d
k2=k2+k∗a1dk2=k2+k∗a1d
kk为任意整数，这时新的k1,k2k1,k2仍满足①式。

证明：
将新的k1,k2k1,k2带入式子得:

(k1+k∗a2d)∗a1+(k2+k∗a1d)∗(−a2)=m2−m1(k1+k∗a2d)∗a1+(k2+k∗a1d)∗(−a2)=m2−m1
拆出来：

k1∗a1+k∗a2∗a1d+k2∗(−a2)+k∗a1∗(−a2)d=m2−m1k1∗a1+k∗a2∗a1d+k2∗(−a2)+k∗a1∗(−a2)d=m2−m1
交换一下顺序，把负号拆出来：

k1∗a1+k2∗(−a2)+k∗a2∗a1d−k∗a1∗a2d=m2−m1k1∗a1+k2∗(−a2)+k∗a2∗a1d−k∗a1∗a2d=m2−m1
那个同加同减可以消掉：

k1∗a1+k2∗(−a2)=m2−m1k1∗a1+k2∗(−a2)=m2−m1
这个式子和①是一样的，因①成立，故此式也成立。

要找一个最小的非负整数解，我们只需要让

k1=k1% abs(a2d)k1=k1% abs(a2d)
k2=k2% abs(a1d)k2=k2% abs(a1d)
即可找到当前最小的k1,k2k1,k2的解，即此时的kk为00。

QQ：此处为什么要取绝对值呢

AA：因为不知道a2da2d的正负性，我们在原基础上要尽量减多个abs(a2d)abs(a2d)，使其为正整数且最小。

4. 等效替代：
   由②式带入

新的xx为：

x=(k1+k∗a2d)∗a1+m1x=(k1+k∗a2d)∗a1+m1
=k1∗a1+m1+k∗a2∗a1d=k1∗a1+m1+k∗a2∗a1d
=k1∗a1+m1+k∗lcm(a1,a2)=k1∗a1+m1+k∗lcm(a1,a2) ③

QQ:这里，kk都为00了，为什么还要算呢？

AA:因为这只是前两个式子得最小kk，有可能遇到下一个式子后面被迫要扩大

在③中，我们设a0=lcm(a1,a2),m0=k1∗a1+m1a0=lcm(a1,a2),m0=k1∗a1+m1
那么：

③ =k∗a0+m0=k∗a0+m0

这个形式与一开始我们分解的形式是不是特别像呢？

没错！假设之后又来了一个a3,m3a3,m3
我们只需要继续找：

x=k∗a0+m0=k3∗(−a3)+m3x=k∗a0+m0=k3∗(−a3)+m3，那么问题又回到了第一步。

5. 总结
   我们的做法相当于每次考虑合并两个式子，将这nn个式子合并n−1n−1次后变为一个式子。最后剩下的式子就满足我们的答案。

注意：

lcm(a1,a2)lcm(a1,a2)和%a2d%a2d，需要取绝对值。又因为d=gcd(a1,−a2)d=gcd(a1,−a2)，我们不知道a1a1的正负性（可能是上一步推过来的）。

%a2d%a2d，需要取绝对值， 膜负数的话，不会取到正解；

#include
#include
using namespace std;
typedef long long LL;
int n;
LL exgcd(LL a, LL b, LL &x, LL &y){
if(b == 0){
x = 1, y = 0;
return a;
}

LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
1
2
3

}
LL inline mod(LL a, LL b){
return ((a % b) + b) % b;
}
int main(){
scanf(“%d”, &n);
LL a1, m1;
scanf(“%lld%lld”, &a1, &m1);
for(int i = 1; i < n; i++){
LL a2, m2, k1, k2;
scanf(“%lld%lld”, &a2, &m2);
LL d = exgcd(a1, -a2, k1, k2);
if((m2 - m1) % d){ puts(“-1”); return 0; }
k1 = mod(k1 * (m2 - m1) / d, abs(a2 / d));
m1 = k1 * a1 + m1;
a1 = abs(a1 / d * a2);
}
printf(“%lld\n”, m1);
return 0;
}