洛谷 P1217 [USACO1.5] 回文质数 Prime Palindromes

// 第 ① 版：从 a 数到 b，一个一个判「是不是回文」＋「是不是质数」—— 参照物
//
// 这是所有人真实的第一反应，也是**唯一一条和「造回文数」完全无关的路**，
// 本页所有对拍拿它当标准答案。
// ⚠ 顶格 b = 10⁸：光外层就一亿次，每个数还要拆位 + 试除 ⇒ 想都不用想。
#include <bits/stdc++.h>
using namespace std;

static bool isPrime(int x) {
    if (x < 2) return false;
    for (long long i = 2; i * i <= x; i++) if (x % i == 0) return false;
    return true;
}
static bool isPal(int x) {
    int t = x, r = 0;
    while (t) { r = r * 10 + t % 10; t /= 10; }
    return r == x;
}

int main() {
    int a, b;
    if (scanf("%d %d", &a, &b) != 2) return 0;
    for (int x = a; x <= b; x++)
        if (isPal(x) && isPrime(x)) printf("%d\n", x);
    return 0;
}

// P1217 回文质数 —— 正解：**先造回文数，再判质数**
//
// ★★ 关键一步是把两件事的顺序调过来：
//   [a, b] 里最多有 10⁸ 个数，可 **≤ 10⁸ 的回文数只有 19 998 个** ——
//   「枚举回文数」比「枚举所有数」少了四个数量级。
//
// ★★★ 再省一半：**位数是偶数的回文数一定能被 11 整除**（证明见页面第 3 步）
//   ⇒ 偶数位里唯一的质数就是 11 本身。⇒ 真正要试的只有
//   1、3、5、7 位那 9 + 90 + 900 + 9000 = **9999 个**，外加 11。
//
// ⇒ 每个候选再试除到 √x（≤ 3163），总量小到微不足道。
#include <bits/stdc++.h>
using namespace std;

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

/** 把前半段 h 镜像成一个 len 位的回文数 */
static int build(int h, int len) {
    int x = h;
    int rest = len / 2;                     // 要镜像回去的位数
    int t = (len % 2) ? h / 10 : h;         // 奇数位时中间那位不重复
    for (int i = 0; i < rest; i++) { x = x * 10 + t % 10; t /= 10; }
    return x;
}

int main() {
    int a, b;
    if (scanf("%d %d", &a, &b) != 2) return 0;
    for (int len = 1; len <= 9; len++) {
        if (len % 2 == 0) {
            // ★ 偶数位的回文数全都被 11 整除 ⇒ 只有 11 自己是质数
            if (len == 2 && a <= 11 && 11 <= b) printf("11\n");
            continue;
        }
        int half = (len + 1) / 2;                       // 前半段（含中间那位）的位数
        int lo = (half == 1) ? 1 : (int)pow(10, half - 1) + 0.5;
        int hi = (half == 1) ? 9 : (int)pow(10, half) - 0.5;
        for (int h = lo; h <= hi; h++) {
            int x = build(h, len);
            if (x < a) continue;
            if (x > b) break;
            if (isPrime(x)) printf("%d\n", x);
        }
    }
    return 0;
}

// P1217 的度量程序：./p1217Count csv        （本页的数字都出自它）
//
//   pal   : ★★★ ≤ 10⁸ 的回文数一共几个 —— 这一个数就是「把顺序调过来」值多少倍。
//   even  : ★★ 「偶数位的回文数必被 11 整除」——把它们**全部**枚举一遍验证（不是抽样）。
//           ⚠ 顺带给这条漂亮性质**称一次重**：它只值 2 倍，不是主角。
//   ans   : [5, 10⁸] 里回文质数一共几个。
//   ms    : 秒表：正解 ／ 筛法（真在 10⁸ 上筛一次）／ 暴力（在 10⁶ 上量再外推）。
//   mem   : 筛到 10⁸ 要多少内存，题面给多少。
//
// ⚠ 秒表用 steady_clock 在进程内量，正解跑 20 次取平均
//   （[第 38 章那一跤](/sol/p1972/)：亚毫秒的秒表不能只跑一次）。
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;

static const int TOP = 100000000;          // 10⁸

static bool isPrime(int x) {
    if (x < 2) return false;
    if (x % 2 == 0) return x == 2;
    for (int i = 3; (long long)i * i <= x; i += 2) if (x % i == 0) return false;
    return true;
}
static bool isPal(int x) {
    int t = x, r = 0;
    while (t) { r = r * 10 + t % 10; t /= 10; }
    return r == x;
}
static int build(int h, int len) {
    int x = h, rest = len / 2, t = (len % 2) ? h / 10 : h;
    for (int i = 0; i < rest; i++) { x = x * 10 + t % 10; t /= 10; }
    return x;
}

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");

    /* ① 把 ≤ 10⁸ 的回文数全部造出来，按位数奇偶分开数 */
    long long palOdd = 0, palEven = 0, evenNot11 = 0, evenPrime = 0, ansCount = 0;
    int evenPrimeWho = -1;
    for (int len = 1; len <= 9; len++) {
        int half = (len + 1) / 2;
        long long lo = (half == 1) ? 1 : (long long)llround(pow(10, half - 1));
        long long hi = (half == 1) ? 9 : (long long)llround(pow(10, half)) - 1;
        for (long long h = lo; h <= hi; h++) {
            long long x = build((int)h, len);
            if (x > TOP) break;
            if (len % 2) palOdd++;
            else {
                palEven++;
                if (x % 11 != 0) evenNot11++;
                if (isPrime((int)x)) { evenPrime++; evenPrimeWho = (int)x; }
            }
            if (x >= 5 && isPrime((int)x)) ansCount++;
        }
    }

    /* ② 秒表 */
    double usFast = 0;
    {
        auto t0 = steady_clock::now();
        volatile long long sink = 0;
        for (int rep = 0; rep < 20; rep++) {
            long long c = 0;
            for (int len = 1; len <= 9; len++) {
                if (len % 2 == 0) { if (11 >= 5 && 11 <= TOP) c++; continue; }
                int half = (len + 1) / 2;
                long long lo = (half == 1) ? 1 : (long long)llround(pow(10, half - 1));
                long long hi = (half == 1) ? 9 : (long long)llround(pow(10, half)) - 1;
                for (long long h = lo; h <= hi; h++) {
                    long long x = build((int)h, len);
                    if (x > TOP) break;
                    if (x >= 5 && isPrime((int)x)) c++;
                }
            }
            sink = sink + c;
        }
        usFast = duration<double, micro>(steady_clock::now() - t0).count() / 20.0;
    }

    double sv[3], br[3];
    for (int rep = 0; rep < 3; rep++) {
        {
            auto t0 = steady_clock::now();
            vector<char> comp((size_t)TOP + 1, 0);
            for (long long i = 2; i * i <= TOP; i++)
                if (!comp[i]) for (long long j = i * i; j <= TOP; j += i) comp[j] = 1;
            volatile long long c = 0;
            for (int x = 5; x <= TOP; x++) if (!comp[x] && isPal(x)) c = c + 1;
            sv[rep] = duration<double, milli>(steady_clock::now() - t0).count();
        }
        {
            auto t0 = steady_clock::now();
            volatile long long c = 0;
            for (int x = 5; x <= TOP; x++) if (isPal(x) && isPrime(x)) c = c + 1;
            br[rep] = duration<double, milli>(steady_clock::now() - t0).count();
        }
    }
    auto med3 = [](double a, double b, double c) { return max(min(a, b), min(max(a, b), c)); };
    double msSieve = med3(sv[0], sv[1], sv[2]);
    double msBrute = med3(br[0], br[1], br[2]);

    double sieveMB = (double)(TOP + 1) / 1048576.0;

    if (csv) {
        printf("palOdd,%lld\n", palOdd);
        printf("palEven,%lld\n", palEven);
        printf("palAll,%lld\n", palOdd + palEven);
        printf("evenNot11,%lld\n", evenNot11);
        printf("evenPrime,%lld\n", evenPrime);
        printf("evenPrimeWho,%d\n", evenPrimeWho);
        printf("ansCount,%lld\n", ansCount);
        printf("candFast,%lld\n", palOdd + 1);
        printf("gainOrder,%.0f\n", (double)TOP / (double)(palOdd + palEven));
        printf("gainEven,%.2f\n", (double)(palOdd + palEven) / (double)(palOdd + 1));
        printf("usFast,%.0f\n", usFast);
        printf("msSieve,%.0f\n", msSieve);
        printf("msBrute,%.0f\n", msBrute);
        printf("sieveOverBrute,%.2f\n", msSieve / msBrute);
        printf("bruteOverFast,%.0f\n", msBrute * 1000.0 / usFast);
        printf("sieveMB,%.1f\n", sieveMB);
        printf("sieveHeadroom,%.2f\n", 125.0 / sieveMB);
        return 0;
    }

    printf("① ≤ 10⁸ 的回文数：奇数位 %lld 个 + 偶数位 %lld 个 = **%lld 个**\n", palOdd, palEven, palOdd + palEven);
    printf("   ⇒ 「先造回文再判质数」比「一个一个审」少看 %.0f 倍的数\n", (double)TOP / (double)(palOdd + palEven));
    printf("\n② 偶数位的回文数**全部**被 11 整除：%lld 个里有 %lld 个例外\n", palEven, evenNot11);
    printf("   其中是质数的只有 %lld 个，就是 %d\n", evenPrime, evenPrimeWho);
    printf("   ⚠ 而这条漂亮性质只把候选从 %lld 砍到 %lld —— **只值 %.2f 倍**，它不是主角\n",
           palOdd + palEven, palOdd + 1, (double)(palOdd + palEven) / (double)(palOdd + 1));
    printf("\n③ [5, 10⁸] 里的回文质数一共 %lld 个\n", ansCount);
    printf("\n④ 顶格 a = 5、b = 10⁸ 的秒表\n");
    printf("   正解（造回文 + 试除，跑 20 次取平均）：%.0f 微秒\n", usFast);
    printf("   筛法（真在 10⁸ 上筛一次再扫）：%.0f 毫秒，内存 %.1f MB（题面给 125 MB，余量 %.2f 倍）\n",
           msSieve, sieveMB, 125.0 / sieveMB);
    printf("   暴力（一个一个审，真跑 10⁸）：%.0f 毫秒 / 时限 1 秒 ⇒ ⚠ **它没超时，余量只有 %.2f 倍**\n",
           msBrute, 1000.0 / msBrute);
    printf("   ⇒ ★★★ 筛法比暴力还**慢** %.2f 倍 —— 真正要判质数的只有 %lld 个数，而它为一亿个数各划了一遍\n",
           msSieve / msBrute, palOdd + palEven);
    return 0;
}