挑战 Goldbach 猜想

jijidawang · 2024-09-11 17:19:59 · 题解

记号约定：\operatorname{isp}(n) 当 n 为素数时为 1、否则为 0，\operatorname{gpf}(n) 表示 n 的最大素因子。

枚举 x=n\bmod i，则注意到一个 i 满足 n\bmod i=x 当且仅当 i\mid(n-x) 且 i>x。

那么就是要算 \displaystyle\sum_{i=1}^{n-1}\operatorname{isp}(i)\sum_{d\mid(n-i)}\operatorname{isp}(d)[d>i]。注意到对于 i>\sqrt n，\displaystyle\sum_{d\mid(n-i)}\operatorname{isp}(d)[d>i] 最大只可能为 1。所以可以先考虑计算 \displaystyle\sum_{i=1}^n\operatorname{isp}(i)[\operatorname{gpf}(n-i)>i] 再以 O(\sqrt n) 的代价修正答案。

令 f_i=\operatorname{isp}(i),\,g_i=[\operatorname{gpf}(i)+i>n]，则对于一个固定的 n，答案即为卷积 (f\times g)_n。对于多组询问，可以考虑先离线，把所有数按 \operatorname{gpf}(i)+i 排序，使用单调指针动态维护当前的 g。那么只需要维护一个数据结构，支持对 g 单点修改，对 f\times g 单点求值。

此处可以考虑根号重构，令 B 是块长。每 B 次修改真正计算一次 f\times g 的值，那么每次询问时只需要处理 O(B) 个单点修改，这可以在线性时间复杂度内简单处理。假设 n,q 同阶则时间复杂度为 O(\frac nBn\log n+nB)，取 B=\sqrt{n\log n} 得最优复杂度 O(n\sqrt{n\log n})。

然后就能过了~