【PAT甲级 - C++题解】1015 Reversible Primes

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 (<105) 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

题意

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

思路

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

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

正常的秦九韶算法：

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

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

//这里的n是整数
long long res = 0;
while (n)
{
    res = res * d + n % d;  //秦九韶算法
    n /= d;
}

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

代码

#include<bits/stdc++.h>
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;
}