自动搬运

查看原文

来自洛谷，原作者为

	ForgotMe 花与剑无痕，高挂一轮明灯。银蝶染旧梦，生死莫再问。

搬运于2025-08-24 22:45:53，当前版本为作者最后更新于2023-03-12 19:28:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

灵感：来自 UOJ 校验码，想着出一个函数没啥特殊性质的题。

Subtask 1

暴力即可。

Subtask 2

$n=1$，显然是筛 $f$ 的前缀和，这个是平凡的，min25 或者一遍 PN 筛法即可。

这里只讲 PN 筛，可以发现质数处点值是 $f(p)=p$，于是构造 $g(x)=x$ 就行。

其实这里出题人想放过去的只有 PN 筛，但想了想还是算了。

Subtask 3

给的是不会筛 $f$ 前缀和的正解。当然可能也有其他做法。

这里先不讲正解。

Subtask 5

这个东西其实也被出烂了，因为 $k=1$，那么 $f(p^k)=p$，于是可以得出 $f(ij)=\frac{f(i)f(j)}{f(\gcd(i,j))}$。知道这个就很简单了，对 $f(\gcd(i,j))$ 反演即可，做法跟 DZY Loves Math IV 一致，这里不再赘述。

Subtask 4 & 6

开始讲跟正解有关的东西了。

记 $F(n,x)=\sum_{i=1}^n f(ix)$ 。

可以发现不能优美的处理 $f(ij)$ 的原因是 $i$ 和 $j$ 可能有共同的质因子，而且这部分的贡献不能很好用 $\gcd(i,j)$ 去描述。

不如粗暴一点，直接枚举 $i$ 所含有的质因子的幂次（枚举的幂次的含义是 $j$ 含有该质因子的个数），只要确定了这些质因子的幂次，那么剩下的问题就很简单了。

设枚举 $i$ 所含有的质因子幂次后确定后的数是 $x$，那么显然 $j$ 得满足 $\gcd(j,x)=x$。

可以列出下列式子：

$$F(n,i)=\sum_{x}f(ix)\sum_{j=1}^{n/x}[\gcd(i,j)=1]f(j) $$

莫反后可以得到：

$$F(n,i)=\sum_{x}f(ix)\sum_{d|i}\mu(d)F(\lfloor\frac{n}{xd}\rfloor,d) $$

如果直接计算并记忆化 $F$，只能过掉 Subtask4。

注意到 $\sum_{d|i}\mu(d)F(\lfloor\frac{n}{xd}\rfloor,d)$ 可以写成 $F_2(\lfloor\frac{n}{x}\rfloor,i)$，将 $F$ 与 $F_2$ 一起计算并记忆化就能过掉 Subtask6。

Subtask 7 & 8

实际上上面的想法是好的，但是可惜的是 $F$ 与 $F_2$ 的转移量太大了，导致效率低下。

仔细想一想，真的有必要枚举 $x$ 吗。答案显然是不用。

不如直接考虑 $F(n,x)$ 的递推式，取一个质数 $p$ 满足 $p|x$。

考虑剥离出 $p$ 的贡献，设 $x_2$ 为 $x$ 去掉质因子 $p$ 后的数。

如果说知道质因子 $p$ 在计算时的幂次，那就简单了。

考虑容斥，枚举质因子 $p$ 被计算了 $i$ 次，一个简单的想法是剩下的质因子的贡献就是 $F(\lfloor \frac{n}{p^i}\rfloor,x_2)-F(\lfloor \frac{n}{p^{i+1}}\rfloor,x_2)$，但是这是错误的，因为多钦定的那一个 $p$ 也是会造成贡献的，并不能简单的算为 $F(\lfloor \frac{n}{p^{i+1}}\rfloor,x_2)$。不如换个角度，把多钦定的那一个 $p$ 造成的贡献给 $x_2$，也就是 $F(\lfloor \frac{n}{p^{i+1}}\rfloor,x_2\times p)$，可以发现，这样子算的话就对了。

$$F(n,x)=\sum_{i=0}(F(\lfloor \frac{n}{p^i}\rfloor,x_2)-F(\lfloor \frac{n}{p^{i+1}}\rfloor,x_2\times p))\times f(p^i) $$

但是，你肯定会问这个复杂度是多少呢，看上去空间就是 $n\sqrt{m}$ 的吧，这怎么跑？实际上，如果把 $p$ 取为 $x$ 的最大质因子，然后记忆化直接算，状态量和转移量都很少，在接受的范围以内。

极限数据下，转移量和状态量分别是 $26116544$，$1810443$，如果预处理出 $n\times x\le 10^6$ 的 $F$，转移量和状态量下降到 $13139202$，$972667$，可以用来减小常数。实际运行中瓶颈在于 PN 筛，如果使用哈希表记忆化，这个部分的运行速度在 200ms $\sim$ 300ms。

最后提一句，这个做法可以解决任何 $\sum_{i=1}^n \sum_{j=1}^m f(ij)$ （其中 $n$ 比较小，$m$ 比较大，$f$ 是一个积性函数）的题，当然，个人认为这个做法可以直接套在 UOJ 校验码这个题上，虽然不知道是否能过（有兴趣的同学可以去试一试），因为作者和 Kubic 老师都无法估计这个算法的时间复杂度。