中国剩余定理
解法
[left{egin{matrix}
\x equiv b_{1}(mod a_{1})
\x equiv b_{2}(mod a_{2})
\...
\x equiv b_{n}(mod a_{n})
end{matrix}
ight.
]
其中(a_{i})互质，求(x)
结论：在(lcm(prod a_{i}))的剩余系下，有唯一解：
[sum a_{i} imes M_{i} imes M^{-1}_{i}
]
其中，(M_{i}=prod_{j
e i }^{} a_{j}),(M_{i}^{-1})为(M_{i})在((mod a_{i}))下的逆元
不想证了证明先咕了吧
例题
#include<bits/stdc++.h>
#define ll long long
#define maxn 15
using namespace std;
ll n,a[maxn],b[maxn];
ll m=1,ans=0;
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=y-(a/b)*x;
return d;
}
signed int main(){
cin>>n;
for(ll i=1;i<=n;i++) {
cin>>a[i]>>b[i];
m*=a[i];
}
for(ll i=1;i<=n;i++){
ll x=0,y=0;
exgcd(m/a[i],a[i],x,y);
ans=((ans+(m/a[i])*b[i]*x)%m+m)%m;
}
cout<<ans%m<<endl;
return 0;
}
扩展中国剩余定理
解法
用于处理模数不互质的情况
思路是两两合并，最后转化为求(k)次扩展欧几里得，得到式子：
[x=X+k imes lcm(a1+a2)
]
即为
[x equiv X mod(lcm(a_{1},a_{2})
]
至于过程中的合并什么的，就是先用EXGCD把两个方程合并成一个方程放进方程组里：
[x equiv b_{1}(mod a_{1}),x equiv b_{2}(mod a_{2})
]
得到：
[x=k_{1}a_{1}+b_{1}=k_{2}a_{2}+b_{2}
]
移项：
[k_{1}a_{1}+k_{2}a_{2}=b_{2}-b_{1}
]
解出：
[k_{1}a_{1}+k_{2}a_{2} equiv gcd(a_{1},a_{2})
]
有解条件为(gcd(a_{1},a_{2})|b_{2}-b_{1})
然后一直这样合并合并，直到只剩下一个方程，哦如果合并的过程中无解了那就返回-1（虽然这道题的数据保证有解）
例题
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define maxn 100010
#define ll long long
using namespace std;
template<typename T>
inline void read(T &x){
x=0; bool flag=0; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
for(;isdigit(c);c=getchar()) x=x*10+(c^48);
if(flag) x=-x;
}
ll n,a[maxn],b[maxn];
ll qmul(ll a,ll b,ll p){
ll res=0;
for(;b;b>>=1,a=(a+a)%p) if(b&1) res=(res+a)%p;
return res%p;
}
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=y-(a/b)*x;
return d;
}
ll excrt(ll n,ll *a,ll *b){
ll x,y,k,tmp;
ll ans=a[1],m=b[1];
for(int i=2;i<=n;i++){
k=exgcd(m,b[i],x,y);
tmp=((a[i]-ans)%b[i]+b[i])%b[i];
if(tmp%k!=0) return -1; //判断是否无解
ans+=qmul(x,tmp/k,b[i])*m;
m*=b[i]/k;
ans=(ans%m+m)%m;
}
return ans;
}
int main(){
read(n);
for(int i=1;i<=n;i++)
read(b[i]),read(a[i]);//注意把读入反过来了（要不调了半天找不出来错......
cout<<excrt(n,a,b);
return 0;
}