自动搬运

查看原文

来自洛谷，原作者为

	jijidawang And in that light, I find deliverance.

搬运于2025-08-24 23:05:20，当前版本为作者最后更新于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})$。

然后就能过了~