HDU 3579 线性同余方程组

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int MaxM=11;int a[MaxM],b[MaxM];void exgcd(int a,int b,int &d,int &x,int &y){
if(b==0){
x=1; y=0;
d=a;
}
else{
exgcd(b,a%b,d,x,y);
int tmp=x;
x=y;
y=tmp-(a/b)*y;
}
}int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}int main(){
int t; int a1,r1,a2,r2; int aa,bb,cc,dd; int x,y; int g;
scanf("%d",&t);
int n,m;
bool ifhave;
int kase=0;
while(t--){
kase++;
scanf("%d",&m);
g=1;
for(int i=0;i<m;i++){
scanf("%d",&a[i]);
if(i==0){ g=a[i]; continue; }
g=g*a[i]/gcd(g,a[i]);
}
for(int i=0;i<m;i++)
scanf("%d",&b[i]);
a1=a[0]; r1=b[0];
ifhave=true;
for(int i=1;i<m;i++){
a2=a[i]; r2=b[i];
aa=a1; bb=a2; cc=r2-r1;
exgcd(aa,bb,dd,x,y);
if(cc%dd!=0){
ifhave=false;
break;
}
int t=bb/dd;
x=(x*(cc/dd)%t+t)%t;
r1=a1*x+r1;
a1=a1*(a2/dd);
}
printf("Case %d: ",kase);
if(!ifhave)
printf("-1\n");
else{
if(r1==0)
printf("%d\n",g);
else printf("%d\n",r1);
}
}
return 0;
}