中国剩余定理

 1 #include<iostream>
 2 #include<string>
 3 #include<cstdio>
 4 typedef long long ll;
 5 using namespace std;
 6 const int maxn=100000+5;
 7 int n;
 8 ll ai[maxn],bi[maxn];
 9 ll exgcd(ll a,ll b,ll &x,ll &y)
10 {
11     if(b==0){ x=1, y=0; return a;}
12     ll gcd=exgcd(b,a%b,x,y);
13     ll tp=x;
14     x=y, y=tp-a/b*y;
15     return gcd;
16 }
17 ll mult(ll a,ll b,ll mod){
18     long long res=0;
19     while(b>0){
20         if(b&1) res=(res+a)%mod;
21         a=(a+a)%mod;
22         b>>=1;
23     }
24     return res;
25 }
26 ll excrt(){
27     ll x,y;
28     ll ans=bi[1],M=ai[1];
29     for(int i=2;i<=n;++i){
30         ll a=M,b=ai[i],c=(bi[i]-ans%ai[i]+ai[i])%ai[i];
31         ll gcd=exgcd(a,b,x,y);
32         x=mult(x,c/gcd,b/gcd);
33         ans+=x*M;
34         M*=b/gcd;
35         ans=(ans%M+M)%M;
36     }
37     return (ans%M+M)%M;
38 }
39 int main(){
40     cin>>n;
41     for(int i=1;i<=n;++i)
42         cin>>ai[i]>>bi[i];
43     cout<<excrt();
44 }