# 使徒卢克的密码 — 题解

出题人解法：阶乘化简与九底 Miller–Rabin。Codex（GPT-6）：安全模乘、边界和确定性证明；补充等差筛法。

## 从阶乘到素数

令 $f=(p-1)!$ .因为 $p!=pf$ ，根号内为 $(f+1)^2/p^2$ ，根号恰为 $(f+1)/p$ .内层取整是整数，因此

$$H(p)=\left\lfloor\frac{f+1}{p}\right\rfloor-\left\lfloor\frac f p\right\rfloor.$$

两个相邻整数的商的向下取整只可能相同，或相差一；后一种情况恰好发生在 $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 的论文](https://arxiv.org/abs/1207.0063) 给出这一界的验证。固定底范围是正确性的组成部分，不能省略为“多试几次即可”。

模乘用二进制加倍：逐位累加被乘数，再将被乘数加倍取模。每次相加的两个量都小于 $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](std.cpp)，不需要大整数阶乘。

[等差数列筛法](solution-alternative.zh.md) 给出无需伪素数界的独立方法。

[题面](statement.zh.md) · [正式数据计划](tests/plan.json) · [生成器](tests/generate.py) · [测量记录](../../../docs/benchmark-R32.json)