HDU 3579 Hello Kiki

题解：不互质的中国剩余定理

#include <cstdio>
#include <iostream>
#define ll long long
#define maxn 10
using namespace std;
ll c[maxn],m[maxn],n,am,ac,y0,z0,d;
bool ans;
void exgcd(ll a,ll b,ll& d,ll& x,ll& y){
    if (b==0) { d=a,x=1,y=0; }
    else exgcd(b,a%b,d,y,x),y-=x*(a/b); 
}
int main(){
    ll i,t,cas=0;
    scanf("%I64d",&t);
    while (t--){
        ans=true; scanf("%I64d",&n);
        for(i=1;i<=n;i++)scanf("%I64d",&m[i]);
        for(i=1;i<=n;i++)scanf("%I64d",&c[i]);
        am=m[1]; ac=c[1];
        for (i=2; i<=n; i++){
            exgcd(am,m[i],d,y0,z0);
            if ((ac-c[i])%d!=0){ans=false;break;}
            y0=(c[i]-ac)/d*y0;
            y0=((y0%(m[i]/d))+(m[i]/d))%(m[i]/d);
            ac=am*y0+ac,am=am/d*m[i],ac=(ac%am+am)%am;
        }
        if (ac==0) ac=am;
        printf("Case %I64d: ",++cas);
        if (ans) printf("%I64d
",ac);
            else printf("-1
");
    }
    return 0;
}