[USACO1.5] 回文质数 Prime Palindromes 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求按升序输出区间 $[a,b]$ ~[a,b]~ 内所有既是质数又是回文数的整数，每行一个。核心解法是不去枚举区间内的每个整数，而是由回文数的前一半直接构造出全部候选（最大为 $9999999$ ~9999999~，共约 $4450$ ~4450~ 个），再对每个候选试除判素。

分析

核心观察

偶数位数的回文数一定能被 $11$ ~11~ 整除。设回文数有 $2k$ ~2k~ 位，从低位向高位看，第 $i$ ~i~ 位在模 $11$ ~11~ 意义下的权是 $10^{i-1} \equiv (-1)^{i-1}$ ~10^{i-1} \equiv (-1)^{i-1}~；回文性使第 $i$ ~i~ 位与第 $2k+1-i$ ~2k+1-i~ 位数字相同，而这两个下标一奇一偶，符号恰好相反，于是全部逐对抵消，整个数模 $11$ ~11~ 余 $0$ ~0~。唯一的例外是 $11$ ~11~ 本身，它长度虽为偶数却是质数。因此除 $11$ ~11~ 之外，回文质数的位数必定是奇数；又因为 $b \le 10^8$ ~b \le 10^8~，而 $10^8$ ~10^8~ 是 $9$ ~9~ 位数且不是回文数，所以候选只需覆盖 $1, 3, 5, 7$ ~1, 3, 5, 7~ 位，再加上特例 $11$ ~11~。

思路

朴素做法是枚举 $[a,b]$ ~[a,b]~ 内的每个整数并逐一判断回文与质数，区间跨度最大可达 $10^8$ ~10^8~，在 $1$ ~1~ 秒的时限内必然超时。把顺序倒过来即可：先构造回文数，再判素。

长度为 $2k-1$ ~2k-1~ 的回文数完全由前 $k$ ~k~ 位决定。设这前 $k$ ~k~ 位的值为 $h$ ~h~，把 $h$ ~h~ 去掉末位后逆序接在 $h$ ~h~ 之后，就得到

$\displaystyle P(h) = h \cdot 10^{k-1} + \operatorname{rev}\left(\left\lfloor \frac{h}{10} \right\rfloor\right)$

其中 $\operatorname{rev}(t)$ ~\operatorname{rev}(t)~ 表示把 $t$ ~t~ 的十进制串逆序后得到的数，长度不足时在左端补 $0$ ~0~；在这条公式中它表现为普通整数的前导零。例如 $k = 2$ ~k = 2~、 $h = 15$ ~h = 15~ 时 $P(h) = 15 \times 10 + 1 = 151$ ~P(h) = 15 \times 10 + 1 = 151~， $k = 3$ ~k = 3~、 $h = 101$ ~h = 101~ 时 $P(h) = 101 \times 100 + 1 = 10101$ ~P(h) = 101 \times 100 + 1 = 10101~。

枚举范围是 $k = 1, 2, 3, 4$ ~k = 1, 2, 3, 4~ 与 $10^{k-1} \le h \le 10^k - 1$ ~10^{k-1} \le h \le 10^k - 1~。 $k = 1$ ~k = 1~ 时 $h$ ~h~ 本身就是一位数字，必须取遍 $1 \sim 9$ ~1 \sim 9~，否则会漏掉答案 $5$ ~5~； $k \ge 2$ ~k \ge 2~ 时又可以把首位限制为 $\{1, 3, 7, 9\}$ ~\{1, 3, 7, 9\}~，因为回文数的末位等于首位，末位是偶数或 $5$ ~5~ 时（除 $5$ ~5~ 自身外）必为合数。 $k = 1$ ~k = 1~ 给出 $9$ ~9~ 个候选， $11$ ~11~ 给出 $1$ ~1~ 个，三位、五位、七位分别给出 $4 \times 10 = 40$ ~4 \times 10 = 40~、 $4 \times 100 = 400$ ~4 \times 100 = 400~、 $4 \times 1000 = 4000$ ~4 \times 1000 = 4000~ 个，合计 $4450$ ~4450~ 个。按 $k$ ~k~ 递增、同一 $k$ ~k~ 内按 $h$ ~h~ 递增的顺序枚举，候选天然升序，不需要排序。

判素用试除。候选都小于 $10^8$ ~10^8~，而任何合数都有不超过 $\sqrt{10^8} = 10^4$ ~\sqrt{10^8} = 10^4~ 的质因子，所以先用筛法求出 $10^4$ ~10^4~ 以内的质数表，再对候选 $n$ ~n~ 依次试除满足 $p^2 \le n$ ~p^2 \le n~ 的质数 $p$ ~p~ 即可，无需米勒-拉宾之类的算法。

具体示例

以题面样例 $a = 5$ ~a = 5~、 $b = 500$ ~b = 500~ 为例。

枚举阶段	落在 $[5,500]$ ~[5,500]~ 内的候选	判定为质数的部分
$k = 1$ ~k = 1~	$5, 6, 7, 8, 9$ ~5, 6, 7, 8, 9~	$5, 7$ ~5, 7~
特例	$11$ ~11~	$11$ ~11~
$k = 2$ ~k = 2~	$101, 111, \dots, 393$ ~101, 111, \dots, 393~	$101, 131, 151, 181, 191, 313, 353, 373, 383$

$k = 1$ ~k = 1~ 的候选里， $2$ ~2~ 与 $3$ ~3~ 虽然是质数却小于 $a$ ~a~，被区间过滤掉； $1, 4, 6, 8, 9$ ~1, 4, 6, 8, 9~ 不是质数，因此只输出 $5$ ~5~ 与 $7$ ~7~。 $k = 2$ ~k = 2~ 的候选里， $111 = 3 \times 37$ ~111 = 3 \times 37~、 $121 = 11^2$ ~121 = 11^2~、 $141 = 3 \times 47$ ~141 = 3 \times 47~、 $161 = 7 \times 23$ ~161 = 7 \times 23~、 $171 = 3^2 \times 19$ ~171 = 3^2 \times 19~、 $303 = 3 \times 101$ ~303 = 3 \times 101~、 $323 = 17 \times 19$ ~323 = 17 \times 19~、 $333 = 3^2 \times 37$ ~333 = 3^2 \times 37~、 $343 = 7^3$ ~343 = 7^3~、 $363 = 3 \times 11^2$ ~363 = 3 \times 11^2~、 $393 = 3 \times 131$ ~393 = 3 \times 131~ 都被试除排除。到了 $k = 3$ ~k = 3~，最小的五位回文数 $10001$ ~10001~ 已经超过 $b$ ~b~，没有候选落入区间。最终输出的 $12$ ~12~ 个数与样例完全一致。

算法步骤

读入 a 与 b。
用埃氏筛打出 $2 \sim 10^4$ ~2 \sim 10^4~ 的质数表 primes。
依次产生候选：一位数 $1 \sim 9$ ~1 \sim 9~；特例 $11$ ~11~；再令 k 取 $2, 3, 4$ ~2, 3, 4~，把前半 h 从 $10^{k-1}$ ~10^{k-1}~ 枚举到 $10^k - 1$ ~10^k - 1~，跳过首位不属于 $\{1, 3, 7, 9\}$ ~\{1, 3, 7, 9\}~ 的 h，用拼接公式把 h 展开成 $2k-1$ ~2k-1~ 位的回文数 pal。
对每个候选 n，若 n 不在 $[a,b]$ ~[a,b]~ 内则跳过。
用质数表试除 n：若存在质数 p 满足 $p^2 \le n$ ~p^2 \le n~ 且 p 整除 n，则 n 为合数；若试到 $p^2 > n$ ~p^2 > n~ 仍未整除，则 n 为质数。
按候选的产生顺序逐行输出所有质数候选；一个都没有时什么也不输出。

复杂度分析

时间：筛法为 $O(\sqrt{b} \log\log\sqrt{b})$ ~O(\sqrt{b} \log\log\sqrt{b})~；候选共 $C = 4450$ ~C = 4450~ 个，合数候选通常在试除最初几个质数后就被排除，而质数候选必须试除完 $\pi(\sqrt{b}) = 1229$ ~\pi(\sqrt{b}) = 1229~ 个质数，这是主要开销，故总时间为 $O(\sqrt{b} \log\log\sqrt{b} + C \cdot \pi(\sqrt{b}))$ ，与区间长度无关。
空间：筛数组与质数表为 $O(\sqrt{b})$ ~O(\sqrt{b})~，候选无需存储，额外空间与 $b - a$ ~b - a~ 无关。

实现注意事项

一位数候选要取遍 $1 \sim 9$ ~1 \sim 9~，不能套用"首位只能是 $1, 3, 7, 9$ ~1, 3, 7, 9~"的限制，否则会漏掉答案 $5$ ~5~。
$11$ ~11~ 是唯一的偶数位回文质数，必须单独补进候选。
四位、六位、八位回文数一律不生成，它们都被 $11$ ~11~ 整除。像 $[1000, 10000]$ ~[1000, 10000]~ 这样的区间因此没有答案，此时不要输出空行。
试除的终止条件写成 $p^2 > n$ ~p^2 > n~，用整数乘法判断，避免开方带来的精度问题。
质数表只需打到 $10^4$ ~10^4~：候选都小于 $10^8$ ~10^8~，不存在最小质因子大于 $10^4$ ~10^4~ 的合数。
回文数的拼接结果最大为 $9999999$ ~9999999~，仍在 $32$ ~32~ 位整数范围内，但 a、b 可达 $10^8$ ~10^8~，读写与比较建议统一使用 long long。
一位数候选中的 $1$ ~1~ 是回文数但不是质数，判素函数要把小于 $2$ ~2~ 的输入直接判为非质数。
整个值域 $[5, 10^8]$ ~[5, 10^8]~ 内共有 $779$ ~779~ 个答案，输出量最大的测试点就是这个满范围；用一次性的字符串缓冲输出比逐行 endl 更稳妥。

源代码

#include <cstdio>
#include <string>
#include <vector>

namespace {

const int LIMIT = 10000;  // sqrt(10^8) 以内的素数足够判定

std::vector<int> buildPrimes() {
    std::vector<bool> composite(LIMIT + 1, false);
    std::vector<int> primes;
    for (int i = 2; i <= LIMIT; ++i) {
        if (composite[i]) continue;
        primes.push_back(i);
        for (long long j = 1LL * i * i; j <= LIMIT; j += i) composite[j] = true;
    }
    return primes;
}

bool isPrime(long long n, const std::vector<int> &primes) {
    if (n < 2) return false;
    for (int p : primes) {
        if (1LL * p * p > n) break;
        if (n % p == 0) return n == p;
    }
    return true;
}

}  // namespace

int main() {
    long long a = 0, b = 0;
    if (std::scanf("%lld %lld", &a, &b) != 2) return 0;

    const std::vector<int> primes = buildPrimes();

    // 候选回文数按长度递增生成，天然有序
    std::vector<long long> cand;
    for (int d = 1; d <= 9; ++d) cand.push_back(d);  // 长度为 1
    cand.push_back(11);                             // 唯一的偶数长度回文质数

    // 长度为 2k-1 的回文数由前 k 位唯一确定：首位只能是 1、3、7、9
    for (int k = 2; k <= 4; ++k) {
        long long lo = 1;
        for (int i = 1; i < k; ++i) lo *= 10;
        for (long long h = lo; h < lo * 10; ++h) {
            const long long lead = h / lo;
            if (lead != 1 && lead != 3 && lead != 7 && lead != 9) continue;
            long long pal = h, rest = h / 10;
            for (int i = 0; i < k - 1; ++i) {
                pal = pal * 10 + rest % 10;
                rest /= 10;
            }
            cand.push_back(pal);
        }
    }

    std::string out;
    for (long long n : cand) {
        if (n < a || n > b) continue;
        if (!isPrime(n, primes)) continue;
        out += std::to_string(n);
        out += '\n';
    }
    std::fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

import math
import sys

LIMIT = 10000  # sqrt(10^8) 以内的素数足够判定


def build_primes():
    sieve = bytearray([1]) * (LIMIT + 1)
    sieve[0:2] = b"\x00\x00"
    for i in range(2, math.isqrt(LIMIT) + 1):
        if sieve[i]:
            sieve[i * i :: i] = bytearray(len(range(i * i, LIMIT + 1, i)))
    return [i for i in range(2, LIMIT + 1) if sieve[i]]


PRIMES = build_primes()


def is_prime(n):
    if n < 2:
        return False
    for p in PRIMES:
        if p * p > n:
            break
        if n % p == 0:
            return n == p
    return True


def main():
    data = sys.stdin.buffer.read().split()
    if len(data) < 2:
        return
    a, b = int(data[0]), int(data[1])

    # 候选回文数按长度递增生成，天然有序
    cand = list(range(1, 10))  # 长度为 1
    cand.append(11)  # 唯一的偶数长度回文质数

    # 长度为 2k-1 的回文数由前 k 位唯一确定：首位只能是 1、3、7、9
    for k in (2, 3, 4):
        lo = 10 ** (k - 1)
        for h in range(lo, lo * 10):
            lead = h // lo
            if lead != 1 and lead != 3 and lead != 7 and lead != 9:
                continue
            pal = h
            rest = h // 10
            for _ in range(k - 1):
                pal = pal * 10 + rest % 10
                rest //= 10
            cand.append(pal)

    out = [
        str(n) for n in cand if a <= n <= b and is_prime(n)
    ]
    if out:
        sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    main()

目前没有评论。