solution-p7572

· · 题解

假设有 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) 计算的，因此可以减少一半的插值次数。