原题链接
https://pintia.cn/problem-sets/994805342720868352/problems/994805495863296000
思路
这题要求判断一个数在翻转前后是否都是质数。有一个难以理解的地方是在给定进制下的翻转,这是指转成该进制表示的数之后翻转,再将翻转后的数转换回十进制判断。比如11在二进制下的翻转,首先转换为二进制表示形式1011,之后翻转为1101,再转换回十进制为13判断。另外,将十进制转换为其他进制的方法是用原数不断去除以进制数,并将每次得到的余数倒序记录下来,而由于我们还需要再翻转一次,所以在计算时直接依次将余数存在vector中最终得到的就是在给定进制下翻转后的数。
代码如下
代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int num, radix, reverse;
vector<int> result; //1代表Yes,0代表No
cin >> num;
while (num >= 0)
{
reverse = 0; //用于存储翻转后的数
if (num < 2) //1和0
{
result.push_back(0);
cin >> num;
continue; //直接进入下一次循环
}
int flag = 1;
cin >> radix;
for (int i = 2; i < num; i++) //判断原数是否为质数
{
if (num%i == 0)
{
flag = 0;
break;
}
}
vector<int> radixNum;
while (num / radix > 0)
{
radixNum.push_back(num%radix);
num /= radix;
}
radixNum.push_back(num);
int exp = 1;
for (int i = radixNum.size() - 1; i >= 0; i--)
{
reverse += radixNum[i] * exp;
exp *= radix;
}
if (reverse < 2) //1和0
{
result.push_back(0);
cin >> num;
continue; //直接进入下一次循环
}
for (int i = 2; i < reverse; i++) //判断翻转数是否为质数
{
if (reverse % i == 0)
{
flag = 0;
break;
}
}
result.push_back(flag);
cin >> num;
}
for (int i = 0; i < result.size(); i++)
{
if (result[i] == 1)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}