HDU 1431 素數回文 詳解

題目：多組查詢，每組給 a, b (5 ≤ a < b ≤ 100,000,000)，輸出 [a,b] 內所有既是素數又是回文的數。每組輸出後空一行。

核心觀察：回文數極其稀少，可預生成

10⁸ 以內回文數總量：
1位：9、2位：9、3位：90、4位：90、5位：900、6位：900、7位：9000、8位：9000 → 總計 < 20000 個。
其中素數更少。預生成所有 ≤10⁸ 的回文素數，查詢時二分/遍歷輸出即可。

回文數生成策略：構造半邊鏡像

1. 按長度 len = 1..8 生成：
     奇數長：枚舉前 (len+1)/2 位，鏡像後 (len-1)/2 位。
     偶數長：枚舉前 len/2 位，鏡像全部。
     首位不能為 0。
2. 生成的數若 ≤ 10⁸，進行素性測試。

素性測試：試除法優化

對 n ≤ 10⁸，√n ≤ 10000。預篩選出 ≤10000 的素數（~1229 個），試除判斷。
或直接 for(i=2; i*i<=n; ++i)，對 2萬個數極快（總操作 ~2億，預處理階段可接受）。

參考代碼 (C++)

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

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; ++i)
        if (x % i == 0) return false;
    return true;
}

vector palPrimes;

void genPalindromes() {
    // 1-8 位
    for (int len = 1; len <= 8; ++len) {
        int half = (len + 1) / 2;
        int start = pow(10, half - 1);
        int end = pow(10, half);
        for (int i = start; i < end; ++i) {
            string s = to_string(i);
            string rev = s;
            reverse(rev.begin(), rev.end());
            string pal = (len % 2 == 0) ? s + rev : s + rev.substr(1);
            long long val = stoll(pal);
            if (val > 100000000) break;
            if (isPrime(val)) palPrimes.push_back(val);
        }
    }
    sort(palPrimes.begin(), palPrimes.end());
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    genPalindromes();
    int a, b;
    bool first = true;
    while (cin >> a >> b) {
        if (!first) cout << '\n';
        first = false;
        for (int p : palPrimes) {
            if (p >= a && p <= b) cout << p << '\n';
        }
    }
    return 0;
}

關鍵優化與坑點

• 預生成一次，多查詢復用：避免重複計算。
• 回文構造：字符串鏡像最簡潔，避免數學反轉溢出/錯誤。
• 範圍上限：題目 b ≤ 100,000,000，生成時嚴格判斷 val > 1e8 剪枝。
• 輸出格式：每組數據後空一行，最後一組也要有（樣例如此）。用 first 標誌控制。
• 已知回文素數列表：可直接硬編碼 1132 個數（如網上資源），O(1) 查詢最快。

複雜度分析

總結

HDU 1431 是「預生成 + 素性測試」的典型應用。核心洞察：回文數密度極低，將「區間查詢」轉化為「列表篩選」。此技巧廣泛適用於「特殊性質數字查詢」（如迴文平方數、可逆素數、Smith 數等）。注意輸出格式細節（組間空行）與上限邊界（10⁸）。