题目传送门 #

~~这是一道我弟拿给我做题目，本来想着普及−应该挺简单的，结果翻车了~~

题目解读#

本题要求我们找出给定区间内的所有“回文质数”¹。我一看就想着：先筛质数，再判断是不是回文数~~，结果大意失荆州——开了一个占用4G内存的prime[100000000]~~于是我终于注意到了题目中的提示：

说明/提示#

Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文数再判断它们是不是质数（素数）.

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。

题目翻译来自NOCOW。

USACO Training Section 1.5

产生长度为 5 的回文数：
1
for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
2
    for (d2 = 0; d2 <= 9; d2++) {
3
        for (d3 = 0; d3 <= 9; d3++) {
4
          palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
5
        }
6
    }
7
}

于是我便把提示里的代码复制了几份～

AC 代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
// 判断一个数是否为质数
5
bool isPrime(int n) {
6
    if (n < 2) return false;
7
    if (n == 2) return true;
8
    if (n % 2 == 0) return false;
9

10
    for (int i = 3; i * i <= n; i += 2) {
11
        if (n % i == 0) return false;
12
    }
13
    return true;
14
}
15

16
vector<int> palindromes;
17

18
int main() {
19
    int st, ed;
20
    scanf("%d%d", &st, &ed);
21

22
    // 生成所有可能的回文数
23

24
    // 1位回文数
25
    for (int i = 1; i <= 9; i++) {
26
        palindromes.push_back(i);
27
    }
28
    // 偶数位回文数(除了11)都能被11整除，不是回文数
29
    // 2位回文数
30
    palindromes.push_back(11);
31

32
    // 3位回文数
33
    for (int i = 1; i <= 9; i += 2) { // 只考虑奇数开头，偶数开头的必不是质数
34
        for (int j = 0; j <= 9; j++) {
35
            palindromes.push_back(i * 101 + j * 10); // iji形式
36
        }
37
    }
38

39
    // 5位回文数
40
    for (int i = 1; i <= 9; i += 2) {
41
        for (int j = 0; j <= 9; j++) {
42
            for (int k = 0; k <= 9; k++) {
43
                palindromes.push_back(i * 10001 + j * 1010 + k * 100); // ijkji形式
44
            }
45
        }
46
    }
47

48
    // 7位回文数
49
    for (int i = 1; i <= 9; i += 2) {
50
        for (int j = 0; j <= 9; j++) {
51
            for (int k = 0; k <= 9; k++) {
52
                for (int l = 0; l <= 9; l++) {
53
                    palindromes.push_back(i * 1000001 + j * 100010 + k * 10100 + l * 1000); // ijklkji形式
54
                }
55
            }
56
        }
57
    }
58

59
    // 9位回文数（虽然超出了1亿，但为了完整性）
60
    for (int i = 1; i <= 9; i += 2) {
61
        for (int j = 0; j <= 9; j++) {
62
            for (int k = 0; k <= 9; k++) {
63
                for (int l = 0; l <= 9; l++) {
64
                    for (int m = 0; m <= 9; m++) {
65
                        int palindrome = i * 100000001 + j * 10000010 + k * 1000100 + l * 100010 + m * 10000;
66
                        if (palindrome <= 100000000) { // 只添加不超过1亿的
67
                            palindromes.push_back(palindrome);
68
                        }
69
                    }
70
                }
71
            }
72
        }
73
    }
74

75
    // 排序
76
    sort(palindromes.begin(), palindromes.end());
77

78
    // 遍历回文数数组，找出其中的质数并输出
79
    for (int palindrome : palindromes) {
80
        if (palindrome > ed) break;
81
        if (palindrome >= st && isPrime(palindrome)) {
82
            printf("%d\n", palindrome);
83
        }
84
    }
85

86
    return 0;
87
}

Over!

即既是回文数又是质数的数 ↩

题目传送门#

题目解读#

说明/提示#

AC 代码#

Footnotes#

题目传送门 #