「GLR-R4」夏至 题解

· · 题解

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

Subtask 1

暴力即可。

Subtask 2

这里只讲 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 老师都无法估计这个算法的时间复杂度。