题目：

 

题意：

给你任意一个 p 进制下有限位数的数 n，问是否一定能转化成 q 进制下有限位数的数字 m。

解题思路：

显然若 n 为整数，一定可以，那么我们下面分析一下 n 含小数的情况。

设 n 的小数部分为 x，且小数部分共 k 位，第 i 位上的数字为 ai。

那么我们可以将 x 表示成下面式子的形式：

。

而在进制转化中，整数部分是“除基倒取余”，小数部分是“乘基正取整”，且乘到小数部分为0时截止。

于是问题转化成了 x 在什么时候小数部分“乘基”一定会变成0。

由 x 的表达式我们可知，当且仅当乘数中含有 p^k 这个因子时，x 的小数部分才为0。

那么就相当于判断 q^h 中是否含有 p^k 这个因子（h 可无限大）。

又由算术基本定理，p^k 中的质因子一定和 p 中的相同。

所以只要 q 中包含 p 的所有质因子，就必定存在 h 使得 q^h 中包含 p^k 这个因子，从而使问题有解。

那么，如何判断 q 中是否包含 p 的所有质因子呢？

 

朴素方法：

将素数存入prime数组中，然后从a的质因数出发，判断b mod (该质因数) == 0 ?

#include 
     
      #include 
      
       #include 
       
        #include 
        
         int visit[1000006],prime[400006];void GetPrime(){ int cnt=0; memset(visit,0,sizeof(visit)); for(int i=2;i<1000006;i++){  if(!visit[i]){   prime[cnt++]=i;  }  for(int j=0;(j
         
          <1000006);j++){   visit[i*prime[j]]=1;   if(i%prime[j]==0){    break;   }  } }}int main(){ int t,cases=1; scanf("%d",&t); GetPrime();           //素数表 while(t--){  __int64 a,b;  scanf("%I64d %I64d",&a,&b);  int flag=1;  for(int i=0;prime[i]<=(int)sqrt(a)&&prime[i];i++){   int x=prime[i];   if(a%x==0){    if(b%x!=0){     flag=0;     break;    }    while(a%x==0){     a/=x;    }   }  }  if(a!=1&&b%a!=0){    flag=0;   }  printf("Case #%d: ",cases++);  printf(flag? "YES\n":"NO\n"); }}
         
        
       
      
     

 

巧妙方法：

1、若 p 和 q 不互质，则只需要判断 q 中是否包含 p/gcd(p,q) 的所有质因子。

2、若 p 和 q 互质，当且仅当 p = 1 时，q 中包含 p 的所有质因子。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include