莫比乌斯反演
假设现在有一个函数 \(f\)，令 \(F(n) = \sum\limits_{d | n} f(d)\)，如 \(F(1) = f(1), F(4) = f(1) + f(2) + f(4)\)，现在我们要通过 \(F\) 反推 \(f\)，如 \(f(1) = F(1), f(4) = F(4) - F(2)\)，这就是莫比乌斯反演。
可以推出这样的公式：\(F(n) = \sum\limits_{d | n}f(d) \Leftrightarrow f(n) = \sum\limits_{d|n}\mu(d)F(\dfrac nd)\)，其中容斥系数 \(\mu\) 是 莫比乌斯函数。
莫比乌斯函数
定义
\(\mu\) 为莫比乌斯函数，定义为：
\[\mu = \begin{cases}1 & n = 1 \\ 0 & n \text{ 含有平方因数} \\ (-1)^k & \rm{otherwise} \end{cases} \]其中 \(k\) 为 \(n\) 的本质不同质因子数。
性质
-
莫比乌斯函数是积性函数，\(\mu(x \times y) = \mu(x) \times \mu(y)\)。
-
\(\sum\limits_{d | n}\mu(d) = \begin{cases}1 & n = 1 \\ 0 & \rm{otherwise} \end{cases}\)，即 \(\sum\limits_{d | n}\mu(d) = [n = 1]\)。
证明：
设 \(n = \prod\limits_{i = 1}^s p_i^{k_i}, n' = \prod\limits_{i = 1}^sp_i\)，则 \(\sum\limits_{d | n}\mu(d) = \sum\limits_{d | n'}\mu(d) = \sum\limits_{i = 0}^s \dbinom si \cdot (-1)^i\)。
由二项式定理中 \((1 + x)^n = \sum\limits_{i = 0}^n\dbinom nix^i\) 得 \(\sum\limits_{i = 0}^s \dbinom si \cdot (-1)^i = \begin{cases}0 & s \ne 0 \\ 1 & s = 0 \end{cases}\)。
\(s = 0\) 时 \(n = 1\)，得证。
特殊地，我们把 \(\gcd(i, j)\) 带入到 \(n\) 中，可以得到一个结论性的式子：\([\gcd(i, j) = 1] = \sum\limits_{d | \gcd(i, j)}\mu(d)\)。
-
\(\sum\limits_{d | n}\dfrac{\mu(d)}d = \dfrac{\varphi(n)}n\)。
证明：\(n = \sum\limits_{d | n} \varphi(d)\)，套莫比乌斯反演，得 \(\varphi(n) = \sum\limits_{d | n}\mu(d) \cdot \dfrac nd\)。
实现
一般不会用到单个 \(\mu\)，这里只给欧拉筛 \(\mathcal O(n)\) 求 \([1, n]\) 的 \(\mu\) 的方法（其实所有积性函数都可以用欧拉筛线性求）。
int mu[N];
bool vis[N];
vector<int> prime;
void getmu(int n) {
mu[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) vis[i] = 1, prime.emplace_back(i);
for (int p : prime) {
if (p * i > n) continue;
vis[p * i] = 1;
if (i % p == 0) break;
mu[p * i] = -mu[i];
}
}
}
例题
P1447 [NOI2010] 能量采集
求
\[2\sum_{i = 1}^n\sum_{j = 1}^m\gcd(i, j) - nm \]\(n, m \le 10^5\)。
核心问题在求 \(\sum\limits_{i = 1}^n\sum\limits_{j = 1}^m \gcd(i, j)\)。不妨假定 \(n \le m\)。
套路地，我们可以转而枚举 \(\gcd(i ,j)\) 的结果，统计个数。
设 \(f(k) = \sum\limits_{i = 1}^n\sum\limits_{j = 1}^m[\gcd(i, j) = k]\)，然后你会发现这样还是不好做，就得用到这类题的另一个套路——容斥。
设 \(F(k) = \sum\limits_{i = 1}^n\sum\limits_{j = 1}^m[\gcd(i, j)|k]\)，然后你会发现 \(F\) 特别好求，\(F(k) = \lfloor \dfrac nk \rfloor \times \lfloor \dfrac mk \rfloor\)。
再推出 \(F\) 和 \(f\) 的关系，是 \(F(k) = \sum\limits_{k | d}f(d)\)，莫比乌斯反演：
\[f(k) = \sum\limits_{k | d}\mu(\dfrac kd)F(d) =\sum\limits_{d | k}\mu(\dfrac kd)\lfloor \dfrac nk \rfloor \lfloor \dfrac mk \rfloor \]时间复杂度 \(\mathcal O(n \log n)\)。
trick：整除分块。
随便整理一下还能有：
\[f(k) = \sum\limits_{i = 1}^{\lfloor\frac nk\rfloor}\mu(i)\lfloor\dfrac n{ik}\rfloor\lfloor\dfrac m{ik}\rfloor \]然后 \(\lfloor\dfrac n{ik}\rfloor\lfloor\dfrac m{ik}\rfloor\) 相同的 \(i\) 可以放在同一块内计算，常数会小不少，时间复杂度也可以看作是 \(\mathcal O(n \sqrt{\log n})\)。
标签：lfloor,limits,dfrac,sum,容斥,mu,反演,莫比 From： https://www.cnblogs.com/chy12321/p/18003444