中国剩余定理（CRT）模版
#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 long
int 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;
}原文地址：https://blog.csdn.net/summ1ts/article/details/142704909
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！