莫比乌斯反演

洛谷题库 P9118 [春季测试 2023] 幂次

我们有非常易于理解的暴力解法：直接对于 $b=3,4\cdots$，求出所有可以当作底数的 $a$，计算 $a^b$ 后放入数据结构/排序去重；特别处理 $b=2$ 的情况即可。在此不再赘述。

不过，我们注意到若有正整数 $x$，满足 $x>1,x=a_0^{b_0}\ \ (a_0,b_0\in \mathbb N)$，且 $\forall a,b\in\mathbb N,a_0\neq a^b$（即底数 $a_0$ 不可再开根），那么 $\forall b,b\mid b_0,x=(a_0^{b_0/b})^b$。这意味着假如不去重地暴力添加 $\lfloor\sqrt[b]{n}\rfloor$ 到答案中，上文中 $x$ 将被算 $|\{b\mid b_0\equiv 0\pmod b\}|$ 次。

于是这就变成莫反的模板题了：记 $g(b)$ 表示“能被 $a^b$ 表出的 $x$ 之数量”，$f(b_0)$ 表示“恰能被 $x=a_0^{b_0}$ 表出，不可被 $x=a^b,b<b_0$ 表出的 $x$ 的数量”。易得 $g(b)=\sum_{b\mid b_0}f(b_0)$，故 $f(b_0)=\sum_{b_0\mid b}g(b)\mu(b/b_0)$。显然，当 $b>\log_2 n$ 时仅有 $a=1$ 满足 $a^b\leq n$，故我们只需计算 $\lfloor\log_2 n\rfloor$ 个 $b$，最后特判 $a=1$。预处理出 $\mu$ 的值，暴力求取反演式，复杂度为 $\operatorname{O}(\log^2 n)$。

---

其实并不需要这么麻烦。我们根本不需要反演：根据 $g(b)=\sum_{b\mid b_0}f(b_0)$，假若 $\forall b_0,b_0>b,f(b_0)$ 都已经计算完成，那么我们直接得到 $f(b)=g(b)-\sum_{b\mid b_0,b_0>b}f(b_0)$。由 $b$ 从大往小计算即可，复杂度相同。