自动搬运

查看原文

来自洛谷，原作者为

	joke3579 **

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

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

以下是正文

---

优化（？）自 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。