自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 22:07:13，当前版本为作者最后更新于2023-01-28 13:45:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

*800，但是题解做法很怪。

每个质因数的贡献是独立的，$\varphi$ 也可以直接积性拆掉。对于每个质因数 $p$ 的次数 $q$，贡献显然是 $\varphi(p^q)^{(n-n/p^{q+1})^k-(n-n/p^q)^k}$（容斥），就没了。

上面的东西用欧拉定理计算，显然总的计算次数是 $\sum \log_p n=O(n/\log n)$，时间复杂度算是线性的。