powerful number 小记

想学 powerful number 请直接去阅读 zzq 的博客，这篇只是用来水。

可能也是最后一篇博客了。

简介

利用 Powerful Number 可以求部分积性函数 \(F(x)\) 的前缀和。

我们可以构造一个积性函数 \(G(x)\)，使得 \(x\) 为质数时 \(G(x)=F(x)\)，并且 \(G(x)\) 的前缀和可以快速计算。

设有积性函数 \(H(x)\) 使得 \(F=G * H\)，即 \(H=F/G\)。可以发现，\(x\) 为质数时 \(H(x)=0\)，由此可以得到 \(H(x)\neq 0\) 的位置，\(x\) 所有质因子的次数一定 \(\ge 2\)，我们将这样的数称为 powerful number。

可以这样的数不超过 \(\sqrt n\) 个，故可以直接爆搜这样的数。求 \(H(p^e)\) 的点值可以安排类似多项式求逆的东西，\(G(p^e)\) 的点值通常可以 \(O(1)/O(e)\) 得到。

模板/代码

在路上了。

powerful number 小记

原文：https://www.cnblogs.com/farway17/p/13074030.html