给出一个数 n ，再分别给出 2n 个数 a[i],和 r[i]，表示 n个同余方程组：x mod a[i] = r[i] , 求满足方程组的最小正整数 x，若不存在 输出 -1
const int N=100+5; const ll mod=21252; int n,m,t; int i,j,k; ll a[N],r[N]; ll ex_gcd(ll a,ll b,ll &x,ll &y) //ax+by=gcd(a,b) { ll gcd=a; if(!b) x=1,y=0; else { gcd=ex_gcd(b,a%b,y,x); y-=(a/b)*x; } return gcd; } void rep(ll &x,ll mod) { x%=mod; x+=mod; x%=mod; //if(!x) x=mod; //注意 ，这句如果加上，在第 1 步对 x 做取余运算时，会发生很奇怪的错误 } ll China() { ll x,y,a1=a[0],r1=r[0]; for(int i=1;i<n;i++){ ll g=ex_gcd(a1,a[i],x,y); //a1x+a[i]y=r[i]-r1 if( (r[i]-r1)%g ) return -1; x=x*(r[i]-r1)/g; rep(x,a[i]/g); r1=r1+x*a1; //合并 a1=a1*a[i]/g; rep(r1,a1); } if(r1==0) return a1; return r1; } int main() { //IOS; int num=0; rush(){ sd(n); for(i=0;i<n;i++) sll(a[i]); for(i=0;i<n;i++) sll(r[i]); printf("Case %d: ",++num); write( China() ); puts(""); } PAUSE; return 0; }
