自动搬运

查看原文

来自洛谷，原作者为

	Misaka14285 猫猫倒过来读也是猫猫 hhh

搬运于2025-08-24 22:31:08，当前版本为作者最后更新于2022-05-02 23:17:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

假设有 $4$ 个数 $z_i$ 满足 $z_iz_j=z_{x(i,j)}$，可以发现他们的线性组合构成一个交换环，则题目所求为满足 $f(p^c)=p^{kc}z_{pc\bmod 4}$ 的积性函数前缀和。

真恶心考虑 min25 筛。

选取完全积性函数 $h(n)=n^kz'_{n\bmod 4}$，其中 $z'_i$ 满足 $z'_iz'_j=z'_{ij}$。显然有 $[z'_i]h(p)=[z_i]f(p)$。

求 $h$ 的前缀和 $H(n)$ 相当于对所有 $0\le t<4$ 求 $m$ 以内模 $4$ 余 $t$ 的自然数 $k$ 次幂之和。设 $S_{t,x}=\sum_{i\le x}(4i+t)^k$，显然是关于 $x$ 的 $k+1$ 次多项式，拉格朗日插值即可。

总复杂度 $O\left(k^2+k\sqrt n+\dfrac{n^{3/4}}{\ln n}\right)$。

此题的复杂度瓶颈在 $O(k\sqrt n)$ 的拉插。存在如下两个效果显著的卡常：

1. 预处理出插值多项式各项系数。多项式单点求值的常数极小。
2. 由于 $>2$ 的质数 $\bmod 4\in \{1,3\}$，事实上初值将 $[z'_0],[z'_2]h(n)$ 直接赋为 $0$ 只会影响 $[z'_0],[z'_2]G(n)$，而这两项又是可以 $O(1)$ 计算的，因此可以减少一半的插值次数。