给定同余方程组,其中 mi两两互质
⎩⎪⎪⎪⎨⎪⎪⎪⎧x≡a1(modm1)x≡b2(modm2)⋯x≡cn(modmn)
我们尝试构造出一个式子,使得式子满足上列同余方程组
- M=mi⋅m2⋅⋯⋅mn=∏inmi
- Mi=M/mi
- ti=Mi−1,Miti=1(modmi)
x=a1t1M1+a2t2M2+⋯+antnMn+kM=i=1∑naitiMi+kM
-
证明
根据2,我们可以得到 i!=j,Miti=0(modmi)
根据3,我们可以得到 i=j,Miti=ai(modmi)
很显然,它的循环节为M
-
于是我们可以的得出,对于任意i, x=ai(modmi)
int CRT(int a[], int m[], int n) {
int M = 1;
int ans = 0;
for(int i = 1; i <= n; i++) {
M *= m[i];
}
for(int i = 1; i <= n; i++) {
int x, y;
int Mi = M / m[i];
exgcd(Mi, m[i], x, y);
ans = (ans + Mi * x * a[i]) % M;
}
if(ans < 0) ans += M;
return ans;
}
---
为了得到ti,根据裴蜀定理,我们必须满足gcd(mi,Mi)=1 ,但如果mi不互质,则会出现不存在ti的情况
我们考虑当前仅存在两个方程
{x≡a1(modm1)x≡b2(modm2)
将其转换成不定方程
x=mip+a1=m2q+a2
m1p−m2q=a2−a1
如果 a2−a1∣gcd(m1,m2) ,则可通过扩展欧几里得,得到一组可行解(p,q)
则两原方程的组成的新方程组解为 x=m1p(modlcm(m1,m2))
否则由裴蜀定理得知等式无解
long long crt(long long n) {
long long M = b[1], ans = a[1], x, y;
for (int i = 2; i <= n; i++) {
long long z = (a[i] - ans%b[i]+b[i])%b[i];
long long k = exgcd(M, b[i], x, y);
if (z % k)
return -1;
long long c = b[i] / k;
x = mul(x,z/k,c);
ans += x * M;
M = M * c;
ans = (ans%M+M)%M;
}
return (ans % M + M) % M;
}