使徒卢克的密码 — 题解¶
出题人解法：阶乘化简与九底 Miller–Rabin。Codex（GPT-6）：安全模乘、边界和确定性证明；补充等差筛法。
从阶乘到素数¶
令 \(f=(p-1)!\) .因为 \(p!=pf\) ，根号内为 \((f+1)^2/p^2\) ，根号恰为 \((f+1)/p\) .内层取整是整数，因此
两个相邻整数的商的向下取整只可能相同，或相差一；后一种情况恰好发生在 \(f\equiv-1\pmod p\) .\(p=1\) 时直接得到 \(H(1)=1\) ，而 \(H(0)=0\) 是单独给出的定义。
当 \(p\ge2\) 时，Wilson 定理说明该同余式当且仅当 \(p\) 是素数。简要证明：素数模下，非零元素与逆元配对，只有 \(1,-1\) 自配对，乘积为 \(-1\) ；合数 \(p\) 有真素因子 \(q<p\) ，则 \(q\) 整除 \((p-1)!\) ，不可能整除 \((p-1)!+1\) .于是每个参数只需判断是否为 \(1\) 或素数。
确定性 Miller–Rabin¶
对奇数候选写成 \(p-1=d2^s\) ，其中 \(d\) 为奇数。对每个底 \(a\) ，先求 \(x=a^d\bmod p\) ；若 \(x\) 是 \(1\) 或 \(p-1\) 则通过，否则连续平方至多 \(s-1\) 次，要求至少一次得到 \(p-1\) .有任何底不通过即为合数。先处理小素数及其倍数，可避免底等于模数。
采用底 \(2,3,5,7,11,13,17,19,23\) .本题参数最大为 \(204999000000000\) ，低于这九个底的最小共同强伪素数 \(3825123056546413051\) ，因此在本题范围内是确定性判断。Jiang 与 Deng 的论文 给出这一界的验证。固定底范围是正确性的组成部分，不能省略为“多试几次即可”。
模乘用二进制加倍：逐位累加被乘数，再将被乘数加倍取模。每次相加的两个量都小于 \(p<2^{48}\) ，所以无符号 64 位加法安全。不要直接计算两个接近 \(p\) 的数的乘积，也不依赖浮点近似商。
顺序计算每个 \(p=k(G+i-1)+b\) ，将其贡献加到累计值后输出。
正确性¶
公式化简证明了贡献仅由上述素数条件及两个特例决定。Miller–Rabin 在所引确定性范围内准确识别素数，安全模乘准确执行每一步模运算。累计值初始为零，每步恰好加入当前公式项；归纳可得每次输出都是要求的前缀和。
复杂度与贡献¶
记最大参数为 \(U\) .固定九个底下，时间 \(O(N\log^2 U)\) ，额外空间 \(O(1)\) ，不存储输出。原出题人的阶乘转素数、九底 Miller–Rabin 思路予以保留；Codex（GPT-6）补充边界定义、确定性依据、安全模乘、证明及测试。实际程序见 std.cpp，不需要大整数阶乘。
等差数列筛法 给出无需伪素数界的独立方法。