pat

题目

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^5)$ 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

Sample Output:

Yes
Yes
No

这里筛素数用到了bitset，实际上用起来跟数组差不多。要注意虽然题目数据范围是1e5，但是sieve函数里面for循环里的i，j应该为long long类型，因为j=ii可能会溢出。

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
43
44
45
46
47
48

#include <cstdio>
#include <vector>
#include <bitset>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
ll _sieve_size;
bitset<100010> bs;
void (int upperbound){
_sieve_size = upperbound + 1;
bs.set();
bs[0] = bs[1] = 0;
for(ll i = 2;i <= _sieve_size;i++)
if(bs[i])
for(ll j = i i; j <= _sieve_size;j += i)
bs[j] = 0;
}
bool isPrime(int n){ return bs[n]; }
int _reverse(int n, int d){
vi rd;
int res = 0, base = 1;
while(n){
rd.push_back(n % d);
n /= d;
}
for(auto iter = rd.rbegin(); iter != rd.rend(); iter++){
res += (iter) base;
base *= d;
}
return res;
}
int main(){
int N, D, r;
sieve(100005);
while(scanf("%d", &N)){
scanf("%d", &D);
if(N < 0)break;
else if(!isPrime(N)){
printf("Non");
continue;
}
r = _reverse(N, D);
if(isPrime(r)) printf("Yesn");
else printf("Non");
}
return 0;
}

赞微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能