题解 P5106 dkw的lcm

critnos · 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)，时间复杂度算是线性的。