[小记] 线性筛递推积性函数

_Cheems · 2024-02-24 09:31:35 · 个人记录

先说说几个常见的积性函数：\phi,d,s,\mu 等，如果我们知道这些函数在质数次幂时的值，那么可以递推算出其它情况的值。

小引理：记 p 是 a 的最小质因子，k 是 p 在 a 里的最高次幂，则有 \gcd(p^k,\frac a{p^k})=1。这是因为 \frac a{p^k} 里一定不含有 p。

所以对于任意积性函数有 f(a)=f(p^k)*f(\frac a{p^k})，只需维护 k 即可，显然 k(a)=k(a/p)+1。