题目:https://www.luogu.org/problemnew/show/P1495
中国剩余定理模板题,打起来太麻烦了,直接看蓝书P152。主要存代码。
#include<bits/stdc++.h> using namespace std; int n; long long a[20],b[20]; inline long long exgcd(long long a,long long b,long long &x,long long &y){ if(!b){ x=1,y=0;return a; } long long d=exgcd(b,a%b,x,y); long long z=x;x=y;y=z-y*(a/b); return d; } inline long long china(){ long long M=1,ans=0; for(int i=1;i<=n;i++) M*=a[i]; for(int i=1;i<=n;i++){ long long m; long long t,y,d; m=M/a[i];d=exgcd(m,a[i],t,y); ans=(ans+b[i]*m*t)%M; } if(ans<0) ans+=M; return ans%M; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i],&b[i]); printf("%lld",china()); // while(1); return 0; }