“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”——《孙子算经》
中国剩余定理
即求多个同余方程的解。
举个栗子。求一个数x，使得： \[\begin{cases} x≡2\pmod 3\\ x≡3\pmod 5\\ x≡2\pmod {11}\end{cases}\]
设 \(M=3*5*11=165\), \(a1=3\), \(a2=5\), \(a3=11\),
\[ \begin{aligned} M1=M/a1=55\\ M2=M/a2=33\\ M3=M/a3=15 \end{aligned} \]
然后我们再求 \(a\) 的逆元 \(c\)。（扩展欧几里得）
然后结果就是 \((a1*M1*c1 + a2*M2*c2 + a3*M3*c3)\pmod M\)
当然，我们要求的不仅仅是符合3个数的要求。于是我们就可以得到代码：
（变量名和以上有出入） 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
typedef long long ll;
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(!b)d=a,x=1,y=0;
else{
exgcd(b,a%b,d,y,x);
y-=(a/b)*x;
}
}
ll China(int n,ll *m,ll*a)
{
ll M=1,d,y,x=0;
for(int i=0;i<n;i++)M*=m[i];
for(int i=0;i<n;i++){
ll w=M/m[i];
exgcd(m[i],w,d,d,y);
x=(x+y*w*a[i])%M;
}
return (x+M)%M;
}
ll m[15],a[15];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%lld%lld",&m[i],&a[i]);
printf("%lld",China(n,m,a));
return 0;
}
以上是中国剩余定理的内容（CRT）
扩展中国剩余定理（exCRT）
简单来说就是对于每两个同余方程，我们可以把它们合并成一个同余方程，并在每次计入一个新的同余方程的时候得到新的解。我们理性地思考一下，如： \[\begin{cases} x≡y_1(mod m_1)\\ x≡y_2(mod m_2)\\ ...\\ x≡y_n(mod m_n) \end{cases}\] \[M=LCM_{i−1}^{k−1}mi\]
其中 \(m_1,m_2,m_3...m_n\) 为不一定两两互质的整数,求 \(x\) 的最小非负整数解.
假设前 \(n-1\) 项已经求出解为 \(x\)，那么对于第 \(n\) 个式子： \[x+tM≡y_n(mod m_n)\] \(M\) 和 \(y_n\)、\(m_n\)是已知的，我们只需 exgcd 求出 \(x\) 和 \(t\) 就行了。
或者我们把合并感性理解一下，假设原来只有一个同余方程 \[x≡y_1(mod m_1)\Rightarrow x+k_1m_1=y_1\] 我们再加入一个方程 \[x≡y_2(mod m_2)\Rightarrow x+k_2m_2=y_2\] 两者相减，得到 \[k_1m_1-k_2m_2=y_1-y_2\] 再用 exgcd 解得 \(k_1\) 和 \(k_2\) 即可。那么要求 \(x\) 的值回代即可。
那么对于一个新加入的式子就有： \[-k_1m_1+y_1+tm_3=k_3m_3+y_3\] （\(k_1\)、\(m_1\) 和 \(y_1\) 表示上次的 \(x\)）发现新的未知数是 \(t\) 和 \(k_3\)，重新用exgcd求解即可。
当然这里只写了三个式子。想要更多同余方程组的解？请多次 exgcd。这个思维和上面的思维是等价的。
洛谷P4777
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
using namespace std;
typedef long long ll;
inline ll read()
{
bool w=0;ll x=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const ll maxn=1e5+100;
ll y[maxn],m[maxn],n;
inline void exgcd(ll a,ll b,ll &x,ll &y,ll &d){
if(!b)d=a,x=1,y=0;
else exgcd(b,a%b,y,x,d),y-=x*(a/b);
}
ll mul(ll a,ll b,ll mod){
ll res=0;
while(b){
if(b&1)res=(res+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return res;
}
inline ll excrt()
{
ll xx,yy,k;
ll M=m[1],ans=y[1];
for(int i=2;i<=n;i++)
{
ll a=M,b=m[i],c=(y[i]-ans%b+b)%b;//x≡y(mod m)，ans为上一次的解。
ll gcd;
exgcd(a,b,xx,yy,gcd);//tM+km=y-x,c是常数项，xx和yy分别表示t和k
ll bg=b/gcd;//这个是为了exgcd的最后一个步骤，求解出最小非负整数解
if(c%gcd!=0) return -1;
xx=mul(xx,c/gcd,bg);
ans+=xx*M;
M*=bg;//M为前k个m的lcm
ans=(ans%M+M)%M;
}
return (ans%M+M)%M;
}
inline void cried()
{
n=read();
for(int i=1;i<=n;i++)m[i]=read(),y[i]=read();
printf("%lld\n",excrt());
}
}
int main()
{
star::cried();
return 0;
}
