# 使徒卢克的密码 — 补充题解

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

## 筛出等差数列中的合数

令 $P=kG+b$ 、$U=P+k(N-1)$ 、$B=\lfloor\sqrt U\rfloor$ .先用 Eratosthenes 筛法枚举不超过 $B$ 的素数 $q$ ，再标记数列 $P+ki$ 中可被 $q$ 整除的项。

- 若 $q\mid k$ 且 $q\nmid P$ ，没有这样的项。
- 若 $q\mid k$ 且 $q\mid P$ ，每一项都可整除。
- 否则扩展欧几里得求 $k$ 模 $q$ 的逆元，解 $i\equiv-Pk^{-1}\pmod q$ ，从最小非负解起每隔 $q$ 项标记一次。

**参数恰好等于 $q$ 时不能标记**：它是素数本身。最后独立处理 $0,1$ ，其他未标记参数贡献一。平方根初值用浮点计算，再用整数平方向上、向下修正；这里平方不会超过 64 位范围。

## 正确性与复杂度

每个被标记且大于一的参数具有真素因子，因此一定是合数。反之，任何合数 $p\le U$ 都有素因子 $q\le\sqrt p\le B$ ；上述同余分类会枚举它的下标，所以不会漏标。前缀累计与标准方法相同。

一个便于核查的上界是 $O((B+N)\log U)$ 时间：筛本身为 $O(B\log\log B)$ ，每个素数的扩展欧几里得为 $O(\log U)$ ；非整除步长的标记次数合计至多 $N\sum_{q\le B}1/q+O(B)$ ，整除步长的素因子至多 $O(\log U)$ 个。位数组使用 $O(B+N)$ 位，另有常数个整数。

它避免使用固定底的强伪素数界，适合作为独立验证算法；初始化和求逆在本题往往比标准方法更贵。正式数据五轮实测在公布时限内。方法和 [alternative.cpp](alternative.cpp) 由 Codex（GPT-6）补充；[标准题解](solution.zh.md) 给出共同的公式化简。

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