【PAT甲级】1015 Reversible Primes

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：PAT题解集合
📝原题地址：题目详情 - 1015 Reversible Primes (pintia.cn)
🔑中文翻译：可逆质数
📣专栏定位：为想考甲级PAT的小伙伴整理常考算法题解，祝大家都能取得满分！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

1015 Reversible Primes

A reversible prime in any number system is a prime whose “reverse” in that number system is also a prime. For example in the decimal system 73 is a reversible prime because its reverse 37 is also a prime.

Now given any two positive integers N (<10⁵) and D (1<D≤10), you are supposed to tell if N is a reversible prime with radix D.

Input Specification:

The input file consists of several test cases. Each case occupies a line which contains two integers N and D. The input is finished by a negative N.

Output Specification:

For each test case, print in one line Yes if N is a reversible prime with radix D, or No if not.

Sample Input:

73 10
23 2
23 10
-2
1
2
3
4

Sample Output:

Yes
Yes
No
1
2
3

题意

这道题给定一个 N 和 D ，需要我们先将 N 转换成 D 进制，然后将数字反转再转换为十进制，判断最终这个数字是不是质数，如果 N 和这个数字都是质数，则就是逆转质数，输出 Yes ；反之，输出 No 。

思路

按正常步骤是要先将 N 转换成 D 进制数，然后再进行反转操作，然后再转换成十进制数来判断该数是否为质数。

但其实可以将这三步转换成一步来做，利用秦九韶算法可以很巧妙地得到结果。

正常的秦九韶算法：

假设给定一个 d 进制 abc ，那么我要转化成十进制的公式为：$a\ast d^2+b\ast d^1+c$ ，放到循环中其实就是：

//假设n为字符串
long long res = 0;
for(auto x : n)
	res = res * d + x - '0';
1
2
3
4

上面循环是从 n 的最高位开始计算，但是我们现在可以反着来，从 n 的最低位开始计算，这要就达到了反转的效果，而且得到的结果也是十进制。

//这里的n是整数
long long res = 0;
while (n)
{
    res = res * d + n % d;	//秦九韶算法
    n /= d;
}
1
2
3
4
5
6
7

另外，反转前和反转后的两个数都要判断是否为质数。

代码

#include
using namespace std;

typedef long long LL;

//判断是否为质数
bool is_prime(int x)
{
    if (x == 1)    return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;
    return true;
}

bool check(int n, int d)
{
    //先判断该数是不是质数
    if (!is_prime(n)) return false;

    //先转换成D进制再反转然后再转换回十进制
    LL r = 0;
    while (n)
    {
        r = r * d + n % d;	//秦九韶算法
        n /= d;
    }

    //判断反转后的数是不是质数
    return is_prime(r);
}

int main()
{
    int n, d;
    while (cin >> n >> d, n >= 1)
    {
        if (check(n, d))  puts("Yes");
        else puts("No");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42