洛谷模版题

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=20;int n,a[N],b[N];int exgcd(int a,int b,int &x,int &y){if(!b){x=1,y=0;return a;}int d=exgcd(b,a%b,x,y),t=x;x=y,y=t-a/b*y;return d;
}int qmul(int a,int b,int p){//快速乘，防止爆long longint res=0;while(b){if(b&1) (res+=a)%=p;b>>=1,a=(a+a)%p;}return res;
}int CRT(){int res=1,ans=0;for(int i=1;i<=n;i++) res*=a[i];for(int i=1;i<=n;i++){int m=res/a[i],x,y;exgcd(m,a[i],x,y);x=(x%a[i]+a[i])%a[i];//x可能为负数(ans+=qmul(qmul(b[i],m,res),x,res))%=res;}return ans;
}signed main(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i]>>b[i];cout<<CRT()<<endl;return 0;
}