题意: 给出A和B,一有限小数的A进制数转换成B进制数也是有限小数的判定。
我觉得如果进制转换做的好点的话,这种题应该不难。
解法:一个小数的A 进制可以表示为:1/(A^1)+1/(A^2)+1/(A^3).....转换成B进制就是不断的乘B直到为0;(1/(A^1)+1/(A^2)+1/(A^3).....)*B^m,进一步化简,要是结果为有限小数,则B^m/(A^n)必须整除,所以A中的质因子在B中都要出现。
#include <iostream> #include <cstring> #include <cstdio> using namespace std; long long num[1000009]; long long pri[1000004]; int k=1; void prim() { memset(num,0,sizeof(num)); k=1; for(int i=2;i<=500000;i++) { if(num[i]==0) { pri[k++]=i; for(int j=i*2;j<=1000004;j+=i) num[j]=1; } } } int main() { prim(); int cas; cin>>cas; long long a,b; int ca=1; while(cas--) { cin>>a>>b; cout<<"Case #"<<ca++<<": "; int flag=1; for(int i=1;i<=k&&(pri[i]*pri[i]<=a);i++) { if(a%pri[i]==0) { while(a%pri[i]==0) a/=pri[i]; if(b%pri[i]!=0) { flag=0; } } } if(b%a!=0)flag=0; if(flag==1) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }