hdu 3579 Hello Kiki

本文主要是介绍hdu 3579 Hello Kiki，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

同 poj 2891 那道题 也是除数不一定互质的中国剩余定理，但有细节问题，所以做的时候wa了十几发。。

#include<stdio.h>
#define LL __int64void exgcd(LL a,LL b,LL& d,LL& x,LL& y)
{if(!b){d=a;x=1;y=0;}else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}
LL gcd(LL a,LL b)
{if(!b){return a;}gcd(b,a%b);
}LL M[55],A[55];LL China(int r)
{LL dm,i,a,b,x,y,d;LL c,c1,c2;a=M[0];c1=A[0];for(i=1; i<r; i++){b=M[i];c2=A[i];exgcd(a,b,d,x,y);c=c2-c1;if(c%d) return -1;dm=b/d;x=((x*(c/d))%dm+dm)%dm;c1=a*x+c1;a=a*dm;}if(c1==0){c1=1;for(i=0;i<r;i++)c1=c1*M[i]/gcd(c1,M[i]);}return c1;
}
int main()
{int T,n,t=0;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%I64d",&M[i]);}for(int i=0;i<n;i++){scanf("%I64d",&A[i]);}LL ans=China(n);printf("Case %d: %I64d\n",++t,ans);}return 0;
}

这篇关于hdu 3579 Hello Kiki的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---