Codeforces 171F 解密题：反素数查找与打表技巧

题目背景：一道「加密」的神题

Codeforces 171F 的题面乍看全是乱码：
qd ucyhf yi q fhycu dkcruh mxeiu huluhiu yi q tyvvuhudj fhycu dkcruh...

实际上这是凯撒密码（字母 +10 偏移）。解密后题意为：求第 n 个反素数（n ≤ 11184）。反素数定义：数字反转后仍为素数，且不等于原数（如 13 ↔ 31）。

解题思路

1. 破解题面

编写小程序将每个字符 -10（或 +16）还原英文，得到完整题目描述。

2. 确定搜索上界

通过打表发现：第 11184 个反素数为 999983。因此只需在 1,000,000 范围内预处理所有反素数。

3. 预处理算法

• 埃氏筛法或试除法判断素性
• 反转函数 rev(x) 计算数字逆序
• 筛选条件：x != rev(x) && isPrime(x) && isPrime(rev(x))
• 存入数组 a[]，下标即序号

核心代码实现

#include <stdio.h>
#include <math.h>

__int64 prime[10000];
__int64 a[1222222];

// 试除法判断素数
__int64 sushu(__int64 a) {
    __int64 k = sqrt(a);
    for (__int64 i = 2; i <= k; i++)
        if (a % i == 0) return 0;
    return 1;
}

// 数字反转
__int64 rev(__int64 sum) {
    __int64 now = 0;
    while (sum) {
        now *= 10;
        now += sum % 10;
        sum /= 10;
    }
    return now;
}

int main() {
    __int64 l1 = 1;
    // 预处理 100万以内所有反素数
    for (__int64 i = 0; i < 1000000; i++) {
        if (i != rev(i) && sushu(i) && sushu(rev(i))) {
            a[l1++] = i;
        }
    }

    __int64 n;
    while (scanf("%I64d", &n) != EOF) {
        printf("%I64d\n", a[n]);
    }
    return 0;
}

关键点总结

• 题面解密：竞赛中遇到乱码优先尝试凯撒/替换密码
• 打表预处理：离线计算上界，在线 O(1) 答题
• 反素数性质：排除回文素数（如 11, 101），仅保留严格反转对
• 数据范围：11184 个反素数全在 100万内，数组开 1222222 绰绰有余

扩展思考

若 n 更大（如 10^6），需用埃氏筛预处理素数表 + 并行筛选，或利用反素数稀疏性质直接生成候选数。本题展示了「读懂题目」有时比算法本身更关键的趣味案例。