中国剩余定理((CRT))
考虑一个同余方程组
其中(b_1,b_2,dots,b_n)两两互质。
令(m = prodlimits_{i = 1}^n b_i)，(M_i = frac{m}{b_i})，(t_i)是同余方程(xM_i equiv 1 (mod b_i))的一个解
那么上面那个方程组的解为(sumlimits_{i = 1}^{n} a_i M_i t_i)。
证明：
考虑(sum)中的一项(i)，对于(k = i)显然有(a_i M_i t_i equiv a_k (mod b_k))，若(k ot = i)，则(a_i M_i t_i equiv 0 (mod b_k))（因为(M_i)是其他(b)的乘积）。
所以上面(Sigma)中的(n)项各会满足一个方程，且不会对其他有影响，故(x = sumlimits_{i = 1}^{n} a_i M_i t_i)是一组合法解。
证毕。
另外，(x)是在(mod m)意义下的解，即解集可以表示为({x + km : k in })。
(Code):
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mult(ll a,ll b,ll c){
if (b>a) swap(a,b);
ll ret=0; for (;b;b>>=1,a=a*2%c) if (b&1) ret=(ret+a)%c;
return ret;
}
void exgcd(ll a,ll b,ll &x,ll &y){
if (b==0){x=1,y=0;return;}
else{
exgcd(b,a%b,x,y);
ll tmp=x; x=y; y=tmp-a/b*x;
}
}
ll a[110],b[110]; int n;
ll CRT(){
ll m=1; for (int i=1;i<=n;i++)m*=b[i];
for (int i=1;i<=n;i++) a[i]=(a[i]%m+m)%m;
ll ans=0;
for (int i=1;i<=n;i++){
ll Mi=m/b[i],t,tmp;
exgcd(Mi,b[i],t,tmp);
t=(t%m+m)%m;
ans=(ans+mult(Mi,mult(t,a[i],m),m))%m;
}
return ans;
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
for (int i=1;i<=n;i++) scanf("%lld",&b[i]);
printf("%lld
",CRT());
return 0;
}
扩展中国剩余定理((ExCRT))
还是这个方程组，现在不保证(b)互质了。。。咋办？
借一点归纳法的想法，假设我们现在已经算出了前(s-1)个方程的一个解解(x)，我们令(m_{k} = LCM_{i = 1}^{k} b_i)（即前(k)个(b)的最小公倍数），那么前(s-1)个方程的解就可以表示为(Ans_{s-1} = { x + k cdot m_{s-1} : k in })。
那么前(s)个方程的解一定是(Ans_{s-1})的子集，即(Ans_s subset Ans_{s-1})
换句话说，我们需要找到一个(k)，使得(x + k cdot m_{s-1} equiv a_s (mod b_s))，令(x' = x + k cdot m_{s-1})，那么(Ans_{s} = { x' + k' cdot m_s : k' in })
容易发现这样的(Ans_{s})一定是(Ans_{s-1})的子集。
如何找(k)呢？
把上面的个方程变一变，就是一个线性同余方程(k cdot m_{s-1} equiv a_x = x (mod b_s))，扩欧算一下就好了。
具体看板子题：（这个......偷了个懒......直接开了__int128，总之(excrt)那块正常看就好了...）
#include <bits/stdc++.h>
using namespace std;
template<class T> inline T RD(){
T x=0,f=1;char ch=getchar();while (!isdigit(ch)){f=ch=='-'?-f:f;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
}
template<class T> inline void output(T x){
if (x<0){putchar('-');x=-x;}
if (x>9) output(x/10); putchar(x%10+48);
}
#define RI RD<int>()
#define RL RD<long long>()
typedef __int128 ll;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
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,x,y),tmp=x; x=y,y=tmp-a/b*y;
return d;
}
ll mult(ll a,ll b,ll m){
ll ret=0; for (a%=m;b;b>>=1,a=a*2%m)if (b&1) ret=(ret+a)%m;
return ret;
}
ll getans(ll a,ll b,ll m){
ll x,y,d=exgcd(a,m,x,y);
if (b%d!=0) return -1;
x=mult(x,b/d,m);
return (x%m+m)%m;
}
const int N=1e5+10;
int n;
ll a[N],b[N];
ll excrt(){
ll lcm=b[1],ans=a[1]; // 前s个b的lcm，和当前的答案
for (int i=2;i<=n;i++){ // 上面说的 s
ll k1=lcm,k2=((a[i]-ans)%b[i]+b[i])%b[i],k=getans(k1,k2,b[i]);
// 上面说的同余方程
if (k==-1){puts("FFF"); return -1;} // 无解（好像那题保证有解。。。）
ans+=k*lcm;
lcm=b[i]/gcd(lcm,b[i])*lcm;
ans=(ans%lcm+lcm)%lcm;
}
return (ans%lcm+lcm)%lcm;
}
int main(){
n=RI;for (int i=1;i<=n;i++) b[i]=RL,a[i]=RL,a[i]%=b[i];
output(excrt());
return 0;
}