题目分析:
给一个A进制的有限小数,能否转化成B进制的有限小数,给出A,B,如果能,输出YES,否则输出NO
X/A^i-----Y/B^j.........化成,A^i*X/(A^i*B^j).....可以看出如果A中所有的质因数,在B中都出现了,就是YES
1.先求出,A和B的最大公约数X,然后,将A不要断除以temp=gcd(A,X),,,最后剩下的就是 A中独有而B中没有的质因数,如果a==1 则YES
代码:
#include<iostream> #include<cstdio> #include<cmath> using namespace std; __int64 gcd(__int64 x,__int64 y) { return y==0?x:gcd(y,x%y); } int main() { int T; __int64 a,b; scanf("%d",&T); for(int t=1;t<=T;t++) { scanf("%I64d %I64d",&a,&b); __int64 x=gcd(a,b); __int64 temp=gcd(a,x); while(1) //while(gcd(a,x)!=gcd(a/temp,x))错过56 14是反例 { a=a/temp; if(a==1) break; temp=gcd(a,x); if(temp==1) break; } //printf("a=%d***\n",a); if(a==1) printf("Case #%d: YES\n",t); else printf("Case #%d: NO\n",t); } //system("pause"); return 0; } //有错误,结束循环的判断条件想错了 #include<iostream> #include<cstdio> #include<cmath> using namespace std; __int64 gcd(__int64 x,__int64 y) { return y==0?x:gcd(y,x%y); } int main() { int T; __int64 a,b; scanf("%d",&T); for(int t=1;t<=T;t++) { scanf("%I64d %I64d",&a,&b); __int64 x=gcd(a,b); __int64 temp=gcd(a,x); while(gcd(a,x)!=gcd(a/temp,x))//56 14...这组是反例, { a=a/temp; temp=gcd(a,x); } printf("a=%d***\n",a); if(a==1) printf("Case #%d: YES\n",t); else printf("Case #%d: NO\n",t); } //system("pause"); return 0; }