PAT甲级 - 1015 Reversible Primes (进制转换＆素数判断)

Link

题意：判断一个数N是否是D进制内的翻转素数，即其在D进制内翻转后依旧是素数。

思路：思路很简单，但是题意有点容易被误解，即当前N为十进制数，首先N必须是质数；再者其转换成D进制数后翻转，再变成十进制数后依旧得是素数才满足。

代码实现：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5+10;

int x, d;

string radix_to_ten(int radix, string s){  // radix->10
    int res = s[0]-'0';
    for(int i = 1; i < s.size(); i ++){
        res *= radix;
        res += s[i]-'0';
    }
    return to_string(res);
}

string ten_to_radix(string s, int radix){  // 10->radix
    int x = stoi(s);
    string res;
    while(x){
        res += (x%radix)+'0';
        x /= radix;
    }
    reverse(res.begin(), res.end());
    return res;
}
;
bool prime[N];
void is_prime() {
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;
    for(int i = 2; i < N; i++) {
        if(prime[i]) {
            for(int j = i + i; j < N; j += i) {
                prime[j] = false;
            }
        }
    }
}

signed main()
{
    is_prime();
    while(cin >> x){
        if(x<0) break;
        cin >> d;
        bool a = prime[x];
        string x_tmp = ten_to_radix(to_string(x), d); // 再转成d进制
        reverse(x_tmp.begin(), x_tmp.end()); // 再翻转
        int xx = stoi(radix_to_ten(d, x_tmp));  // 再转成10进制
        bool b = prime[xx];
        cout << (a&&b?"Yes":"No") << endl;
    }

    return 0;
}