中国剩余定理

 1 //Vijos 1164 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<iostream> 6 #include<algorithm> 7 #define rep(i,n) for(int i=0;i<n;++i) 8 #define F(i,j,n) for(int i=j;i<=n;++i) 9 #define D(i,j,n) for(int i=j;i>=n;--i)10 using namespace std;11 12 int getint(){13     int v=0,sign=1; char ch=getchar();14     while(ch<‘0‘||ch>‘9‘) {if (ch==‘-‘) sign=-1; ch=getchar();}15     while(ch>=‘0‘&&ch<=‘9‘) {v=v*10+ch-‘0‘; ch=getchar();}16     return v*=sign;17 }18 typedef long long LL;19 /*******************tamplate********************/20 21 void exgcd(LL a,LL b,LL &d,LL &x,LL &y){22     if(!b){ d=a; x=1; y=0; }23     else { exgcd(b,a%b,d,y,x); y-=x*(a/b); }24 }25 LL china(int n,int *a,int *m){26     LL M=1,d,y,x=0;27     F(i,1,n) M*=m[i];28     F(i,1,n){29         LL w=M/m[i];30         exgcd(m[i],w,d,d,y);31         x=(x+y*w*a[i])%M;32     }33     return (x+M)%M;34 }35 int a[11],b[11];36 int main(){37     int n=getint();38     F(i,1,n) a[i]=getint(),b[i]=getint();39     printf("%lld\n",china(n,b,a));40     return 0;41 }