PAT甲级1015.

目录

A1015

题目

样例

输入:

73 10
23 2
23 10
-2

输出:

Yes
Yes
No

思路和坑点

　　典型的进制转换，但是多了一个reverse的过程，但是十进制转化成给定r进制的时候，每一位获取顺序是反着的，因此刚好可以和再转化为十进制的过程联合起来写在一起。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
bool prime[MAXN];
void getprime() {                                //筛选法，获取素数表 
    fill(prime,prime+MAXN,true);
    prime[0]=prime[1]=false;
    for(int i=2;i<MAXN;i++){
        if(prime[i]){
            for(int j=i+i;j<MAXN;j+=i)
                prime[j]=false;
        }
    }
}
int torever(int n,int r){                        //获得逆转数的十进制 
    int ret=0;
    do{                                            //按照转化为r进制数的方法，获取每一位，然后同时转化为对应的十进制 
        ret=ret*r+n%r;
        n/=r;
    }while(n!=0);
    return ret;
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    getprime();
    while(1){
        int n,r;
        scanf("%d",&n);
        if(n>=0){                                //符合条件时进行判定，不符合输入条件时直接结束循环 
            scanf("%d",&r);
            if(prime[n]&&prime[torever(n,r)])
                puts("Yes");
            else
                puts("No");
        }
        else
            break;
    } 
    return 0;
}