loolu5的专栏

可以用中国剩余定理也可以用线性同余方程组，，时间分别是0.028和0.036

在这个问题里逆元一定有解

#include<bits/stdc++.h>using namespace std;long long p[15];//ans==r[i](mod p[i])long long r[15];int n;void extgcd(long long a,long long b,long long &d,long long &x,long long &y)//return gcd(a,b)(==a*x+b*y){if(!b)d=a,x=1,y=0;else{extgcd(b,a%b,d,y,x);y-=x*(a/b);}}long long chinese_remainder(){long long M=1;for(int i=0; i<n; i++)M*=p[i];long long ans=0;long long m;long long d,x,y;for(int i=0; i<n; i++){m=M/p[i];extgcd(m,p[i],d,x,y);ans=(ans+r[i]*m*x)%M;}return (ans+M)%M;}int main(void){int t,Case=0;scanf("%d",&t);while(t–){scanf("%d",&n);for(int i=0; i<n; i++)scanf("%lld%lld",&p[i],&r[i]);printf("Case %d: %lld\n",++Case,chinese_remainder());}return 0;}

#include<bits/stdc++.h>using namespace std;vector<long long>A,B,M;//A[i]*x==B[i](mod M[i])long long gcd(long long a,long long b){return b==0?a:gcd(b,a%b);}void extgcd(long long a,long long b,long long &d,long long &x,long long &y)//return gcd(a,b)(==a*x+b*y){if(!b)d=a,x=1,y=0;else{extgcd(b,a%b,d,y,x);y-=x*(a/b);}}long long mod_inverse(long long a,long long m){long long x,y,d;extgcd(a,m,d,x,y);return (x%m+m)%m;}pair<long long,long long>linear_congruence(const vector<long long>&A,const vector<long long>&B,const vector<long long>&M){long long x=0,m=1;for(int i=0; i<A.size(); i++){long long a=A[i]*m,b=B[i]-A[i]*x,d=gcd(M[i],a);if(b%d!=0)return pair<long long,long long>(0,-1);long long t=b/d*mod_inverse(a/d,M[i]/d)%(M[i]/d);x=x+m*t;m*=M[i]/d;}return pair<long long,long long>((x%m+m)%m,m);}int main(void){int t,Case=0;int n;scanf("%d",&t);while(t–){scanf("%d",&n);long long m,b;A.clear();B.clear();M.clear();for(int i=0; i<n; i++){scanf("%lld%lld",&m,&b);A.push_back(1);B.push_back(b);M.push_back(m);}printf("Case %d: %lld\n",++Case,linear_congruence(A,B,M).first);}return 0;}

让所有的愁向后飞去。请不要回头去追你因该向前奔跑，因为快乐在前方!