前往：我自己搭建的博客
题目
洛谷P4777扩展中国剩余定理（EXCRT）
题解
由于mi之间不保证互质,所以Mi和mi也不一定互质,所以不能用exgcd求Mi(mod mi)的逆元。考虑用数学归纳法，假设已经求出了前i个方程构成的方程组的一个解X0，通解为X。
考虑第（i+1）个方程，设前（i+1）个方程构成的方程组的一个解为x’。
要找出一个k，使x’满足所有条件，成为新解。将上式变形，就成了一个以k为未知数的线性同余方程，可以用exgcd判断方程是否有解，并进一步求出解。
求M时,为了防止溢出,可以求所有mi的最小公倍数。
此题数据较大，即使是在模意义下，乘法操作时仍然可能溢出，所以要使用“快（龟）速乘”。类似快速幂的原理，将乘法中的其中一个数二进制分解，然后逐步相乘。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n;
ll x,y,M,ans;
ll a[maxn],m[maxn];
inline ll mul(ll a,ll b,ll p) //a*b(mod p) , a可以小于0,b必须大于0
{
ll ans=0;
for( ;b;b>>=1)
{
if(b&1) ans=(ans+a)%p;
a=(a<<1)%p;
}
return ans;
}
ll exgcd(ll a,ll b)
{
if(!b) {x=1,y=0; return a;}
ll d=exgcd(b,a%b);
ll z=x; x=y; y=z-(a/b)*y;
return d;
}
inline ll EXCRT()
{
M=m[1],ans=a[1];
for(int i=2;i<=n;i++)
{
ll gcd=exgcd(M,m[i]),c=((a[i]-ans)%m[i]+m[i])%m[i];
x=(x%m[i]+m[i])%m[i];
x=mul(c/gcd,x,m[i]/gcd);
x=(x%(m[i]/gcd)+m[i]/gcd)%(m[i]/gcd);
ans+=x*M;
M*=m[i]/gcd;
ans=(ans%M+M)%M;
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&m[i],&a[i]);
printf("%lld\n",EXCRT());
return 0;
}
