莫比乌斯反演

知识体系

---

什么是莫比乌斯函数

我们假设现在手上有两个函数$F(x)$和$g(x)$，其中$F(x)$很好求,$g(x)$很难求。已知$F(x)$可以表示成$g(x)$的和的形式，那么我们用$F(x)$反过来去求$g(x)$的过程就叫做莫比乌斯反演。

有什么形式

A.求(题目戳我)(这个是乱入的)

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\phi(i*j)$$
B.求(题目戳我)
$$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)$$

刷基础

• [CQOI]余数求和
• [POI2007]ZAP-Queries 余数求和升级版
• gcd之和
• [NOI2010]能量采集 gcd之和升级版

刷提高

• Loves Math IV