注意这里是构造了一个解,ti由于Mi与mi互质,可以用ExGCD求解
例题:https://www.acwing.com/problem/content/1300/
模板:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=10; int m[N],a[N]; LL ExGCD(LL a,LL b,LL &x,LL &y) { if(b==0) { x=1,y=0; return a; } LL xx,yy; LL gcd=ExGCD(b,a%b,xx,yy); x=yy; y=xx-a/b*yy; return gcd; } LL Inv(LL num,LL MOD) { LL res,k; ExGCD(num,MOD,res,k); return res; } int main() { int n;cin>>n; long long M=1; for(int i=0;i<n;i++) { cin>>m[i]>>a[i]; M*=m[i]; } LL res=0; for(int i=0;i<n;i++) { res+=a[i]*M/m[i]*Inv(M/m[i],m[i]); } res=(res%M+M)%M; //要求最小正整数解,故结果对M取正余数 //因为M是全部a的最小公倍数,对于线性同余方城,取模后不影响结果 cout<<res<<endl; }View Code
标签:int,res,LL,ExGCD,yy,算法,long,同余,AcWing From: https://www.cnblogs.com/ydUESTC/p/16753498.html