hdu 1788 Chinese remainder theorem again 披着中国剩余定理的皮

Chinese remainder theorem againTime Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 912    Accepted Submission(s): 329


Problem DescriptionInputOutputSample InputSample OutputAuthorSourceRecommend/*N % MI = MI - a 原式等价于 (N + a) % MI = 0 所以此题为求 M0 到 MI 的最小公倍数 (注意精度问题,用__int64) 一开始 我把这题直接套中国剩余定理去做了 样例也过了 但是WA 然后一直困惑于这点其实这个题和中国剩余定理不沾边 本质其实是一个求最小公倍数*/#include<stdio.h>__int64 gcd(__int64 a,__int64 b){if(b==0) return a;return gcd(b,a%b);}int main(){__int64 n,i,k,ans,num;while(scanf("%I64d %I64d",&n,&k)!=EOF){ans=1;if(!n&&!k) break;for(i=0;i<n;i++){scanf("%I64d",&num);ans=ans/gcd(ans,num)*num;}printf("%I64d\n",ans-k);}return 0;}