莫比乌斯反演杂谈

分类: 文章 • 2024-09-11 15:41:28

常见函数的狄利克雷卷积：
莫比乌斯反演杂谈

关于gcd(i,j)

g c d (i, j) = \sum_{d | g c d (i, j)} φ (d)

如果在一些奇怪的位置，可设其为d，进行枚举。
也可以设其为p(x)，进行反演。

关于gcd(i,j)==1
等价于

\sum_{d | g c d (i, j)} μ (d)

关于同时枚举p和d
可以枚举它们的积 $T$ ，设 $d | T$ ，这样它们就是 $d$ 和 $\frac{T}{d}$ 了