P12390 题解

· · 题解

优化（？）自 NaCly_Fish 题解。

根据基础数论知识，\mathrm{inv}(x, p^k) \neq 0 当且仅当 \gcd(x, p^k) = 1，进一步地，其等价于 \gcd(x, p) = 1。从而我们需要计算的就是

\sum_{i = 1}^n \dfrac{[\gcd(i, p) = 1]}{i} = \sum_{i = p\lfloor n/p\rfloor}^n \dfrac{[\gcd(i, p) = 1]}{i} + \sum_{t = 0}^{p - 1} [\gcd(t, p) = 1] \sum_{i = 0}^{\lfloor n/p\rfloor - 1} \dfrac{1}{ip + t}

前半部分可以直接枚举 i 计算，只需要考虑后半部分。

通过二项式展开，我们可以将 (ip + t)^{-1} 视为以 p 为形式变元的幂级数，而 \bmod\ p^k 的条件只是将幂级数在 k 次幂处截断为多项式，并给了多项式的系数一个模数。那么不妨枚举与 p 互质的 t（这也指出 t 自然有逆），考察截断在 k 次项的多项式

F_{t,n}(x) = \sum_{i = 0}^{n} \dfrac{1}{ix + t} = \dfrac{1}{t} \sum_{j = 0}^{k - 1} (-x/t)^j\sum_{i = 0}^{n} i^j

我们需要的 F_{t, n} 中 n 都相同，那么如果预处理了指数为 0, \dots, k - 1 的自然数幂和，我们就能对任意 t 以 O(k) 的复杂度计算 F_{t, n}(p)。这是简单的：我们已经知道了

\sum_{i = 1}^n i^k = \sum_{i = 0}^k {k\brace i} \dfrac{(n + 1)^{\underline{i + 1}}}{i + 1}

再注意到 n + 1, \dots, n - i + 1 这 i + 1 个数中有且仅有一个数是 i + 1 的倍数，我们就能 O(k^2) 地预处理下降幂的部分，从而 O(k^2) 计算出每个需要的自然数幂和。到这里，我们就能 O(pk) 计算第二部分了。

最后是一些保证复杂度的实现细节：求逆可以用非递归 exgcd 实现，单次复杂度 O(k\log p)，而且可以减少很多常数；第一部分可以简单做到 O(p + k \log p)，只需按照一次求逆求乘法逆元的方式写；[\gcd(i, p) = 1] 和 i^{-1} 都是积性的，可以线性筛出来，复杂度是至多 O(pk) 的。

总时间复杂度 O(k^2 + pk)。

Submission。