使徒卢克的密码 — 补充题解¶
出题人解法：阶乘化简与九底 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 由 Codex（GPT-6）补充；标准题解 给出共同的公式化简。