HDU 1788 中国剩余定理
题目大意:一个正整数N除以M1余(M1 - a),除以M2余(M2-a),除以M3余(M3-a),总之, 除以MI余(MI-a),其中(a<Mi<100i=1,2,…I),求满足条件的最小的数。
题目分析 :通过 N % Mi = Mi-a 可以知道:(N+a)%Mi== 0;
即N+a使所有Mi的最小公倍数,所有我们只要求一个最小公倍数就可以了。
错误分析:此题目只能定义数据类型__int64,而不能定义为long long类型的,不然就WA;至于原因百度后得到的答案:__int 64由微软来确保是64位,8个字节,不可移植。
long long与平台相关,可能是 8字节也可能不是。
- #include<cstdio>
- #include<cstring>
- using namespace std;
- __int64 gcd(__int64 a,__int64 b)//求最大公约数
- {
- if(b==0)return a;
- return gcd(b,a%b);
- }
- __int64 lcm(__int64 ans,__int64 m)//求最小公倍数
- {
- return ans/gcd(ans,m)*m;
- }
- int main()
- {
- int a,b,m;//a是mi的个数,m是除数;
- while(scanf("%d%d",&a,&b),a||b)
- {
- __int64 ans=1;
- for(int i=0;i<a;i++)
- {
- scanf("%d",&m);
- ans=lcm(ans,m);
- }
- printf("%I64d\n",ans-b);//即N+a是所有Mi的最小公倍数,只要求一个最小公倍数lcm-b就可以了。
- }
- return 0;
- }