【PAT甲级】1015 Reversible Primes (20 分)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：

每次输入两个正整数N,D直到N是负数停止输入（N<1e5,1<D<=10）,如果N是一个素数并且将N转化为D进制后逆转再转化为十进制后依然是个素数的话输出Yes，否则输出No。

trick：

判断转化后的数是不是1，1不是素数，如果转化后不是1说明转化前也不会是1（第一个测试点错误原因）。

AAAAAccepted code：

 #include<bits/stdc++.h>

 using namespace std;

 int main(){

     int n,d;

     while(cin>>n){

         if(n<)

             break;

         cin>>d;

         int flag=;

         for(int i=;i*i<=n;++i)

             if(n%i==)

                 flag=;

         int a[]={};

         int cnt=;

         while(n){

             a[++cnt]=n%d;

             n/=d;

         }

         int x=;

         for(int i=;i<=cnt;++i){

             x*=d;

             x+=a[i];

         }

         if(x==)

             flag=;

         for(int i=;i*i<=x;++i)

             if(x%i==)

                 flag=;

         if(flag)

             cout<<"No"<<"\n";

         else

             cout<<"Yes"<<"\n";

     }

     return ;

 }