积性函数，莫比乌斯反演（二）

[[ slider_text ]]

[[ item.c ]]

积性函数，莫比乌斯反演（二）

发布时间 2024-12-02 作者：zhangminchen 来源：算法小站

莫比乌斯反演

## 欧拉筛求积性函数
### 求积性函数的例子
**[线性筛求积性函数](https://ac.nowcoder.com/acm/contest/22769/A)**
求正整数$$n$$的所有正因数的个数，$$q$$次询问

**算法分析**
这实际上就是求$$d(n)$$
```bash
void solve() {
    vector<int> f(maxn, 0);
    f[1] = 1;

auto calc = [&](int p, int k) -> int {
        return k + 1;
    };

vector<int> primes;
    auto mulfun = [&]() -> void {
        vector<int> notprime(maxn, 0), cnt(maxn, 0);

for (int i = 2; i < maxn; i++) {
            if (!notprime[i]) primes.push_back(i), f[i] = calc(i, 1), cnt[i] = 1;
            for (auto p : primes) {
                if (p * i >= maxn) break;
                notprime[p * i] = 1;
                if (i % p == 0) {
                    cnt[i * p] = cnt[i] + 1;
                    f[i * p] = f[i] / calc(p, cnt[i]) * calc(p, cnt[i]+1);
                    break;
                }
                cnt[i * p] = 1;
                f[i * p] = f[i] * calc(p, 1);
            }
        }
    };
    mulfun();
}
```

### 一些问题
#### 华华给月月出题
**[华华给月月出题](https://ac.nowcoder.com/acm/contest/22769/B)**
求解
```math
\bigoplus_{i = 1}^{N} (i^N \bmod (10^9 + 7))
```

**算法分析**
> 暴力怎么做？

可以直接快速幂计算$$\\{1^N, 2^N, 3^N, \cdots, N^N\\}$$，然后再全部异或起来，复杂度是$$O(n\log n)$$

> 有没有可以优化的点？

注意到，计算$$x^N, x \in [1, N]$$，记$$f(x) = x^N$$，不难发现$$f(x)$$是积性函数
因为$$f(pq) = p^N \cdot q^N = f(p)f(q)$$
与此同时，它又是一个**完全积性函数**，因为上述条件不需要$$(p, q) = 1$$，对$$\forall p, q$$都成立

完全积性函数，求解的时候**可以记忆化**，具体来说，$$f(i\cdot p) = f(i) \cdot f(p)$$
由于我们从小到大遍历，$$p$$是当前$$\leqslant i$$的素数集合，所以遍历到`f[i]`的时候，`f[p]`已经被求出来了
可以直接记忆化
```bash
void solve() {
    vector<int> primes;
    auto mulfun = [&]() -> void {
        vector<int> notprime(maxn, 0);

for (int i = 2; i < maxn; i++) {
            if (!notprime[i]) primes.push_back(i), f[i] = calc(i, 1);
            for (auto p : primes) {
                if (p * i >= maxn) break;
                notprime[p * i] = 1;
                if (i % p == 0) {
                    f[i * p] = f[i] * f[p];
                    break;
                }
                f[i * p] = f[i] * f[p];
            }
        }
    };
    mulfun();
	// 其他代码省略
}
```

## Codeforces Round 757 (Div. 2)
这场比赛有一个比较有意思的积性函数的题目
### C
**[C. Divan and bitwise operations](https://codeforces.com/contest/1614/problem/C)**
给定一个序列`a[1...n]`，都是非负的，现在我们考虑它的**每一个非空子集**，把每个子集的`a`的值先异或起来
然后把子集$$\oplus$$的和相加，得到一个`coziness`值，现在我们忘记了这个`coziness`
但是给出$$m$$个输入，每个输入`l r x`表示$$(a\_l \mid a\_{l+1} \mid \cdots \mid a\_r) = x$$，即按位 or
要求你构造一个$$a$$，求出可能的`coziness`
注意，这里保证**a 中的每个元素，至少会包含在**$$m$$个输入的其中一个，这个条件很重要

#### 算法分析
不难发现，这个问题应该一位一位来考虑，不妨假设当前正在构造$$a_i$$，那么有什么限制？
```math

a_i \oplus \left<\empty \right> \\
a_i \oplus \left<\{a_1\}, \{a_2\}, \{a_3\}, \cdots, \{a_n\} \right> \\
a_i \oplus \left< \{ a_1 \oplus a_2 \}, \{a_1 \oplus a_3\}, \cdots, \{a_{n-1} \oplus a_n\} \right> \\
\vdots
```

如果$$a_i$$的第$$k$$位是$$0$$，那么无所谓
如果$$a_i$$的第$$k$$位是$$1$$，那么要看异或下来这个`1`**能不能保住**，假设这个`1`可以保住
那么第$$k$$位的贡献就是 $$2^k \cdot (\binom{n-1}{0} + \binom{n-1}{1} + \cdots + \binom{n-1}{n-1}) = 2^k \cdot 2^{n-1}$$

如果第$$k$$位是`1`的数有`cnt`个，那么第$$k$$位的贡献就是$$cnt \cdot 2^k \cdot 2^{n-1}$$

> 这样，我们对每一个$$k$$位，考虑这一位能不能**保住 1**

检查每一个限制`l r x`，如果$$x$$的第$$k$$位是`0`，那么说明`a[l...r]`这个区间的数，
无论如何都不能提供`1`，标记`invalid[l...r] = 1`
把每一个限制检查完了之后，发现有**至少一个**位置`invalid(j) == false`，那么说明`a[j]`的第$$k$$位可以提供`1`
构造的时候，只需要让`a[j] |= (1 << k)`即可

因为位和位之间相互独立，除了`a[j]`第`k`位是`1`，其他位，即使能填`1`我们也让它填`0`
这样位和位之间是不影响的，并且能够保证第`k`位一定可以贡献一个`1`

> 怎么标记`invalid[l...r] = 1`？

很简单，用差分数组，差分数组`invalid[l] += 1, invalid[r+1] -= 1`，然后对差分数组求一遍前缀和
看一下存不存在`invalid(j) = false`，存在答案就$$+ 2^{k} \cdot 2^{n-1}$$

### E
**[E. Bash Plays with Functions](https://codeforces.com/contest/757/problem/E)**
定义$$f_0(n)$$是$$p \cdot q = n$$并且$$gcd(p, q) = 1$$的$$(p, q)$$的对数

定义$$\displaystyle f\_{r+1}(n) = \sum\_{u \cdot v = n} \dfrac{f\_r(u) + f\_r(v)}{2}$$

给定`q`次询问，每次输出$$f_r(n) \bmod (10^9 + 7)$$

#### 前置结论

> 对于 $$g(m) = \sum\_{d \mid m}f(d)$$，$$g(m)$$是积性，$$\Rightarrow f(d)$$也是积性
反过来也成立

归纳假设，不妨令$$m = m_1m_2, d = d_1d_2$$，其中$$(d_1, d_2) = 1, (m_1, m_2) = 1$$

1）首先
```math
\displaystyle
g(m_1m_2) = \sum_{d \mid (m_1m_2)}f(d) = \sum_{d_1 \mid m_1}\sum_{d_2 \mid m_2} f(d_1d_2)
```
2）注意到
```math
\displaystyle
\sum_{d_1\mid m_1} \sum_{d_2 \mid m_2} f(d_1d_2) = \sum_{d_1, d_2 \neq m_1, m_2} f(d_1d_2) + f(m_1m_2) 
= \sum_{d_1\mid m_1} f(d_1) \sum_{d_2\mid m_2}f(d_2) - f(m_1)f(m_2) + f(m_1m_2) 
\\ = g(m_1)g(m_2) - f(m_1)f(m_2) + f(m_1m_2)
```
而$$g(m_1m_2) = g(m_1)g(m_2)$$，从而$$f(m_1m_2) - f(m_1)f(m_2) = 0$$

> 如果$$f(m), g(m)$$为积性函数，那么$$h(m) = \sum\_{d \mid m} f(d)g(\dfrac{m}{d})$$也是积性函数

```math
\displaystyle
h(m_1m_2) = \sum_{d \mid (m_1m_2)}f(d)g(\dfrac{m_1m_2}{d}) = \sum_{(d_1,d_2) \neq (m_1, m_2)} f(d_1d_2)g(\dfrac{m_1m_2}{d_1d_2}) + f(m_1m_2)g(\dfrac{m_1m_2}{m_1m_2})

\\ = \sum_{d_1\mid m_1}f(d_1)g(\frac{m_1}{d_1}) \sum_{d_2 \mid m_2}f(d_2)g(\frac{m_2}{d_2}) - f(m_1)g(\frac{m_1}{m_1}) \cdot f(m_2)g(\frac{m_2}{m_2}) + f(m_1m_2)g(1) 
\\ = \sum_{d_1 \mid m_1}f(d_1)g(\frac{m_1}{d_1}) \sum_{d_2 \mid m_2} f(d_2)g(\frac{m_2}{d_2}) = h(m_1)h(m_2)
```

#### 算法分析

> 怎么算 $$f_0(n)$$

实际上，我们只要考虑`(p 能选的方案数) * (q 能选的方案数)`即可
对$$n$$进行素因子分解，假设有$$m$$个不同的素因子，要想$$P \cdot Q = n$$
那么我们从$$m$$个素因子中，选择$$i$$个分给$$P$$，剩下$$m - i$$个唯一确定，只能分给$$Q$$

答案就是$$\displaystyle \binom{m}{0} + \binom{m}{1} + \binom{m}{2} + \cdots + \binom{m}{m} = 2^m$$

形式化地说
```math
\displaystyle
f_0(n) = \sum_{d \mid n} \begin{cases} 1 \quad [(\frac{n}{d}, d) = 1] \\ 0 \quad [(\frac{n}{d}, d) \neq 1] \end{cases} = 2^{m}
```

> 怎么算$$f_r(n)$$

注意到递推$$\displaystyle f\_{r+1}(n) = \sum\_{d \mid n} \dfrac{2f\_r(d)}{2} = \sum\_{d\mid n} f_r(d)$$

因为$$f_0(n) = 2^m$$，其中$$m$$表示$$n$$**不同素因子**的个数，它与$$n$$无关，并且它是积性的
因此，根据归纳假设，$$f_r(n)$$也是积性的

> 原问题转化成什么问题？

对于$$q$$次询问，对$$n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$$，转化为求
```math
\displaystyle
\prod_{i = 1}^{k} f_r(p_k^{\alpha_k})
```
可以先预处理打表出所有的$$f_r(p_k^{\alpha_k})$$，然后乘起来，复杂度是$$O(q\log n)$$

再进一步观察，不难发现，$$f_1(p^{\alpha}) = f_0(p^0) + f_0(p^1) + \cdots + f_0(p^{\alpha}) = 1 + 2 \alpha$$

> 怎么计算答案？

注意到$$f_r(p^{\alpha})$$，与$$p$$无关，记$$f(r, \alpha) = f_r(p^{\alpha})$$
1）对于所有的$$r$$，我们有$$f_r(0) = 1$$

2）根据递推$$f(r, \alpha) = f\_r(p^{\alpha}) = \sum\_{p^k \mid p^{\alpha}} f\_{r-1}(p^k) = \sum\_{k \leqslant \alpha} f(r-1, k)$$

实际上就是前缀和，$$f\_r(\alpha) = f\_{r}(\alpha - 1) + f\_{r-1}(\alpha)$$

### 龙哥的问题
**[龙哥的问题](https://ac.nowcoder.com/acm/contest/1030/B)**
给你一个$$n$$，求解$$\sum\_{1 \leqslant i \leqslant n} gcd(i, n)$$

#### 算法分析
不难想到，这种问题一般都需要枚举`gcd`到底等于多少，因为`gcd`首先一定是$$n$$的因子
```math
\displaystyle
ans = \sum_{d \mid n} d \cdot (\text{有多少个 i，满足 gcd(i, n) = d})
```
另外还需要有限制$$i < n, \quad gcd(i, n) = d, \quad \text{i 是 d 的倍数}$$

注意到$$gcd(i, n) = d \Longleftrightarrow gcd(i/d, n/d) = 1$$

实际上，$$ans = \sum\_{d \mid n} d \cdot \phi(\dfrac{n}{d})$$，打表`phi`函数，枚举因子即可求解

但注意到，$$n$$非常大，直接打表不现实，但考虑到$$\sqrt{n}$$不会太大
对每一个$$n$$，枚举因子，对每个因子暴力求$$\phi$$，复杂度好像是$$O(\sqrt{n} \log n)$$

## 莫比乌斯反演
什么是反演？
已知多项式$$F$$，$$G = h(F)$$，即$$F$$通过某种作用，变换成$$G$$
那么如果我已知$$G$$，能不能找到这样的一个$$F$$，使得$$F = h^{-1}(G)$$

> 已知$$f(n) = \sum\_{d\mid n}g(d)$$，能不能通过$$f$$求出$$g$$

```bash
f(1) = g(1)
f(2) = g(1) + g(2)
f(3) = g(1) + g(3)
f(4) = g(1) + g(2) + g(4)
f(5) = g(1) + g(5)
f(6) = g(1) + g(2) + g(3) + g(6)
f(7) = g(1) + g(7)
f(8) = g(1) + g(2) + g(4) + g(8)

不难发现，根据 f 来求 g，可以这样来求

g(1) = f(1)
g(2) = f(2) - f(1)
g(3) = f(3) - f(1)
g(4) = f(4) - f(2)
g(5) = f(5) - f(1)
g(6) = f(6) - f(2)  - f(3) + f(1)
g(7) = f(7) - f(1)
g(8) = f(8) - f(4)
```
不难发现，$$g(n) = f(n) - \sum f(\text{一些 n 的因子})$$

根据这种问题的解决思路，一般可以**从大到小**来考虑每个因子
```math
\displaystyle
g(n) = f(n) - (\sum_{d \mid \text{这个因子}} g(剔除了一个因子)) \\
= f(n) - \sum_{d} f(n \text{ 中剔除了一个因子成为 } d) + (\sum_{d \mid \text{ 因子 }} g( \text{剔除了 2 个因子} )) \\
= f(n) - \sum_{d} f(n \text{ 中剔除了一个因子成为 }d) + \sum_{d} f(n \text{ 剔除了 2 个因子}) - \sum_{d \mid 因子} g(\text{剔除了 3 个因子} )
```

> 再来想一个问题，为什么`g(8) = f(8) - f(4)`，为什么不需要`f(2)`了？通俗点说，上述**剔除的因子**，不能有两个相同的

不难发现
```math
f(p) = g(1) + g(p) \\
f(p^2) = g(1) + g(p) + g(p^2) \\
f(p^3) = g(1) + g(p) + g(p^2) + g(p^3)
```
存在**类似前缀和的递推关系**，$$f(p^k) = f(p^{k-1}) + g(p^k)$$
那么，$$g(p^k) = f(p^k) - f(p^{k-1})$$

由此，$$g(p^k)$$一定可以用**只剔除一个因子**之后的$$f(p^{k-1})$$唯一表示

> 那么，就可以定义莫比乌斯函数了

```math
\mu(d) = \begin{cases}
1 & d = 1 \\
(-1)^k & d=p_1p_2\cdots p_k, d \text{ 是 k 个不同素数的乘积} \\
0 & d\text{ 是 } p^2 \text{ 的倍数} 
\end{cases}
```
**莫比乌斯反演**
```math
\displaystyle
f(n) = \sum_{d \mid n} g(d) \\
\Longleftrightarrow g(n) = \sum_{d \mid n} \mu(\dfrac{n}{d}) f(d)
```

### 环计数问题
假设$$n$$个元素组成一个环，每个元素都是$$1, 2, \cdots, r$$中的一个数
两个环是不同的，当且仅当不能通过旋转使得两个环中，对应的元素都相等，求有多少个这样的环

> 首先考虑序列$$a_1\cdots a_n$$

那么这样的序列很显然有$$r^n$$种，环的个数肯定比这样的序列的个数少，具体怎么对应起来呢？

> 考虑周期性

不妨设$$a_1\cdots a_n$$的周期为$$d$$，那么可以分成若干段，如下的$$d$$段都对应相同的环
```bash
[a(1), a(2), ..., a(d-1), a(d)] [a(1), a(2), ..., a(d-1), a(d)] ......
[a(2), a(3), ..., a(d), a(1)] [a(2), a(3), ..., a(d), a(1)] .....
....
....

// 轮换 d 次，可以有 d 组这样的数，都对应同一个环
```

假设环的方案数为$$f(d)$$，那么我们是否有$$r^n = \sum_d d\cdot f(d)$$呢

我们来看看有什么性质，首先$$d \mid n$$，为什么呢？
不妨假设$$d \nmid n, \quad n = qd + r \ (r < d)$$，那么我们有
```math
a_i = a_{i+d}, \text{ 因为 n 也是一个周期，所以 }  \\
a_i = a_{i+n} = a_{qd + r + i} = a_{r+i}
```
要么$$r = 0$$，要么$$r < d$$并且$$r$$也是一个周期
令$$d$$是环的**最小正周期**，那么我们有 $$\displaystyle r^n = \sum\_{d \mid n} d\cdot f(d)$$

根据莫比乌斯反演，$$\displaystyle nf(n) = \sum\_{d \mid n} \mu(\dfrac{n}{d}) r^d$$
于是我们有
```math
\displaystyle
f(x) = \dfrac{1}{x} \sum_{d \mid x} \mu(\dfrac{x}{d}) \cdot r^d
```
最后的答案是$$ans = \sum\_{d\mid n} f(d)$$

### 莫比乌斯反演的倍数形式
对于$$n$$的倍数$$d$$

```math
\displaystyle
g(n) = \sum_{n \mid d} f(d) \Rightarrow f(n) = \sum_{n \mid d} \mu(\dfrac{d}{n})g(d)
```

> 先给出莫比乌斯函数的求和

先证明一个莫比乌斯函数的性质$$\displaystyle \sum\_{d \mid n} \mu(d) = [n = 1]$$

如果$$d$$有平方因子，忽略
只需要考虑$$d \mid (p_1p_2\cdots p_k)$$，那么我们根据二项式定理，从$$k$$个不同的数中，选$$i$$个

实际上$$\displaystyle \sum\_{d \mid n} \mu(d) = \sum\_{i} \binom{k}{i} (-1)^i = (1-1)^k = 0$$
当然$$n = 1$$的时候，$$\sum\_{d \mid n} \mu(d) = 1$$，证明完毕

> 接下来证明

令$$d = kn$$
```math
\displaystyle
\sum_{n \mid d} \mu(\dfrac{d}{n})g(d) = \sum_{k = 1}^{+\infty} \mu(k)g(nk) = \sum_{k = 1}^{+\infty}\mu(k)\sum_{nk \mid t} f(t) \\
= \sum_{n \mid t}f(t)\sum_{k \mid \frac{t}{n}} \mu(k) = \sum_{n \mid t} f(t) [\dfrac{t}{n} = 1] = f(n)
```

## 莫比乌斯反演练习
### 序列
**[序列](https://ac.nowcoder.com/acm/contest/22769/C)**
求满足$$gcd(x, y) = 1$$，并且$$a(b_x) = b(a_y)$$的数对$$(x, y)$$的数量

#### 算法分析
如果没有 gcd 的限制的话，只需要`for 每一个 b[i]`，哈希表令`cnt[ a(b[i]) ] += 1`
然后再`for 每一个 a[i]`，做一遍查询，查询`cnt[ b(a[i]) ]`出现的次数，加到答案中

> 怎么处理$$\text{gcd}(x, y) = 1$$这个限制？

考虑到$$gcd(x, y) = d$$，那么有$$gcd(x/d, y/d) = 1$$，然后借助欧拉函数$$\phi(y/d)$$之类的，来求解
反过来，对于$$\text{gcd}(x, y) = 1$$，能不能考虑令$$\text{gcd}(xk_x, yk_y) = d$$来求解呢？

> 将条件形式化表示出来

形式化地来看
```math
\displaystyle
\sum_{x\in [1, n], y \in [1, n]} [a(b_x) = b(a_y)][gcd(x, y) = 1]
```

怎么简化条件$$[gcd(x, y) = 1]$$呢？
记$$f(d)$$表示$$\text{gcd}(x, y) = d$$的对数（严格等于$$d$$）
记$$g(d)$$表示$$\text{gcd}(x, y) = d$$**的倍数**的对数，这样限制就少了一些，需要满足的是$$d \mid x, d \mid y$$

这样，$$g(d) = \sum\_{d \mid x, d \mid y, x \in [1, n], y \in [1, n]} [a(b_x) = b(a_y)]$$

那么我们有
```math
\displaystyle
g(d) = \sum_{d \mid d^{\prime}} f(d^{\prime}) = \sum_{d \mid x, d \mid y} [a(b_x) = b(a_y)]
```

根据莫比乌斯反演，我们有
```math
\displaystyle
f(1) = \sum_{1 \mid d, d \in [1, n]} \mu(\dfrac{d}{1})g(d) = \sum_{d = 1}^{n} \mu(d)g(d)
```

这就是我们要求的答案，那么很显然，$$\mu(d)$$可以用积性函数筛法，求解出来
那么$$g(d) = \sum\_{d \mid x, d\mid y} [a(b_x) = b(a_y)]$$
实际上，对$$d = [1, n]$$，枚举每一个$$d$$的倍数$$x$$，复杂度是**调和级数**，$$O(n\log n)$$解决

#### 算法实现
最核心的算法如下
```bash
int main() {
	// 其他代码省略
    vector<ll> g(n+5, 0);
    for (int d = 1; d <= n; d++) {
        map<int, ll> cnt;
        for (int x = d; x <= n; x += d) cnt[ a[b[x]] ] += 1;
        for (int y = d; y <= n; y += d) g[d] += cnt[ b[a[y]] ];
    }
}

// 如果哈希表还卡常，比如卡 map，那么用数组来表示
// 用数组来表示的时候，要记得还原现场
int main() {
	// 其他代码省略
    vector<ll> g(n+5, 0), cnt(n+5, 0);
    for (int d = 1; d <= n; d++) {
        for (int x = d; x <= n; x += d) cnt[ a[b[x]] ] += 1;
        for (int y = d; y <= n; y += d) g[d] += cnt[ b[a[y]] ];
		// 还原现场
		for (int x = d; x <= n; x += d) cnt[ a[b[x]] ] -= 1;
    }
}
```

### ABC162 E
**[Sum of gcd of Tuples](https://ac.nowcoder.com/acm/contest/22769/E)**
求解
```math
\sum_{a_1 = 1}^{k}\sum_{a_2 = 1}^{k} \cdots \sum_{a_n = 1}^{k} \text{gcd}(a_1, a_2, \cdots, a_n) \bmod (10^9 + 7)
```

#### 前置结论
> 关于欧拉函数$$\displaystyle \sum\_{d \mid n} \phi(d) = n$$

证明，令$$f(x)$$表示$$\text{gcd}(?, n) = x$$的$$?$$个数，其中$$? < n$$，那么我们有条件$$gcd(?, n) = x, \ x \mid n$$

等价于$$gcd(\dfrac{?}{x}, \dfrac{n}{x}) = 1$$，相应的$$?$$的个数是$$\phi(\dfrac{n}{x})$$，从而$$f(x) = \phi(\dfrac{n}{x}) \ [x \mid n]$$

另一方面，$$n = \sum\_{i = 1}^{n} f(i)$$ （很显然，因为$$\text{gcd}$$一定是$$\leqslant n$$的）

从而我们有$$n = \sum\_{d \mid n} \phi(\dfrac{n}{d})$$，对称地，$$\sum\_{d\mid n} \phi(d) = n$$

> 推论，$$\displaystyle \sum\_{d \mid n} d \cdot \mu(\dfrac{n}{d}) = \phi(n)$$

很简单，只需要令$$f(n) = n$$，$$f(n) = \sum\_{d \mid n} \phi(d)$$，用莫比乌斯反演即可证明

#### 算法分析
这种问题一般都是枚举`gcd`到底等于多少？不妨设`gcd = d`，那么原式可以写成
```math
\displaystyle
\sum_{d = 1}^{N} d \sum_{\forall i, \ 1 \leqslant a_i \leqslant k} [\text{gcd}(a_1, a_2, \cdots, a_n) = d]
```
即看一下有多少个数以`d`作为`gcd`

> 怎么求解？

令$$\displaystyle f(d) = \sum\_{1\leqslant a_i \leqslant k} [\text{gcd}(a_1, a_2, \cdots, a_n) = d]$$

同样，因为强制$$\text{gcd} = d$$的限制比较多，考虑$$d$$的倍数就简单一些，令
```math
\displaystyle
g(d) = \sum_{d \mid d^{\prime}} f(d^{\prime}) = \sum_{1 \leqslant a_i \leqslant k} [d \mid a_1][d \mid a_2]\cdots [d \mid a_n] \\

= \left( \lfloor \dfrac{k}{d} \rfloor \right)^n
```
根据莫比乌斯反演
```math
\displaystyle
f(d) = \sum_{d \mid d^{\prime}} \mu(\dfrac{d^{\prime}}{d})g(d^{\prime}) = \sum_{d \mid d^{\prime}}\mu(\dfrac{d^{\prime}}{d}) \left(\lfloor \dfrac{k}{d^{\prime}} \rfloor \right)^n
```
从而
```math
\displaystyle
ans = \sum_{d = 1}^{k}d \sum_{d \mid d^{\prime}} \mu(\dfrac{d^{\prime}}{d})\left( \lfloor \dfrac{d^{\prime}}{d} \rfloor \right)^n = \sum_{d^{\prime} = 1}^{k}\left( \lfloor \dfrac{k}{d^{\prime}} \rfloor \right)^n \sum_{d \mid d^{\prime}} d \mu (\dfrac{d^{\prime}}{d}) \\

= \sum_{d^{\prime} = 1}^{k} \left(\lfloor \dfrac{k}{d^{\prime}} \rfloor \right)^n \cdot \phi(d^{\prime})
```

这都可以通过暴力来求解

## 莫比乌斯反演的特殊形式
### 莫比乌斯函数和
> 莫比乌斯函数和$$\displaystyle \sum\_{d \mid n} \mu(d) = [n = 1]$$

对于**[序列](https://ac.nowcoder.com/acm/contest/22769/C)**这个问题，求解
```math
\displaystyle
\sum_{x \in [1, n], y \in [1, n]} [a(b_x) = b(a_y)][gcd(x, y) = 1] \Rightarrow \sum_{x \in [1, n], y \in [1, n]} [a(b_x) = b(a_y)]\sum_{d\mid gcd(x, y)} \mu(d) \\
= \sum_{d = 1}^{n} \mu(d) \sum_{d\mid x, d\mid y} [a(b_x) = b(a_y)]
```
只需要枚举$$d = 1 \to n$$，$$\mu(d)$$可以预处理，至于$$\sum\_{d \mid x, d \mid y} [a(b_x) = b(a_y)]$$，记为$$cnt(d)$$

同样可以枚举$$d$$的倍数，记一下对于每个$$d$$满足条件的有多少个，答案$$\sum\_{d = 1}^{n} \mu(d) \cdot cnt(d)$$

### 欧拉反演
> 欧拉反演$$\displaystyle \sum\_{d \mid n} \phi(d) = n$$

对于**[Sum of gcd of Tuples (Hard)](https://ac.nowcoder.com/acm/contest/22769/E)**这个问题
```math
\displaystyle
\sum_{1 \leqslant a_1, a_2, \cdots, a_n \leqslant k}\text{gcd}(a_1, a_2, \cdots, a_n) = \sum_{1 \leqslant a_1,\cdots, a_n \leqslant k} \sum_{d}\phi(d)[d \mid a_1][d \mid a_2]\cdots [d\mid a_n]

\\ = \sum_{d = 1}^{k} \phi(d) \sum_{a_1\cdots a_n \text{是 b 的倍数}} [d \mid a_1][d \mid a_2]\cdots [d \mid a_n] = \sum_{d = 1}^{k} \phi(d) \lfloor \dfrac{k}{d} \rfloor ^n
```

### Codeforces Round 911 (Div. 2)
**[D. Small GCD](https://codeforces.com/problemset/problem/1900/D)**
**问题描述**
定义
```math
\sum_{i = 1}^{n} \sum_{j = i+1}^{n} \sum_{k = j+1}^{n} f(a_i, a_j, a_k)
```
为$$(a_i, a_j, a_k)$$较小的 2 个数的 gcd，要求你计算$$f$$

**算法分析**
不妨设$$j < i$$，那么有
```math
\displaystyle
\sum_{i = 1}^{n} \sum_{j = 1}^{i-1} \text{gcd}(a_i, a_j) (n - i) = \sum_{i = 1}^{n} (n - i) \cdot \sum_{j = 1}^{i-1} \text{gcd}(a_i, a_j)

\\ = \sum_{i = 1}^{n}(n - i) \sum_{j = 1}^{i-1} \sum_{d \mid gcd(a_i, a_j)} \phi(d) = \sum_{i = 1}^{n}(n - i) \cdot \sum_{d \mid a_i} \phi(d) \sum_{j=1}^{i-1} [d \mid a_j]
```

注意到$$[d\mid a_j]$$已经是一个前缀了，可以遍历$$a_i$$

1）预处理$$a\_i$$所有的因子$$d$$，并打表，同时维护$$cnt(d) = \sum\_{prefix} [d \mid a_j]$$
2）遍历$$a_i$$，枚举$$a_i$$的每个因子$$d$$，然后统计答案，将$$\phi(d) \cdot cnt(d)$$加到答案中
做完了之后，`cnt[d] += 1`

**算法实现**
```bash
void solve() {
    sort(a.begin()+1, a.end());

vector<vector<int> > fac(n+1);
    for (int i = 1; i <= n; i++) {
        auto x = a[i];
        auto &factors = fac[i];

for (int d = 1; d * d <= x; d++) {
            if (x % d) continue;
            factors.push_back(d);
            if (d * d != x) factors.push_back(x / d);
        }
    }

ll ans = 0;
    vector<ll> cnt(maxn, 0);
    for (int i = 1; i <= n; i++) {
        ll val = 1LL * (n - i);
        for (auto d : fac[i]) ans += 1LL * phi[d] * cnt[d] * val;
        for (auto d : fac[i]) cnt[d] += 1;
    }
    printf("%lld\n", ans);
}
```

上一篇：积性函数，莫比乌斯反演（一）下一篇：最大流和匹配

看完文章有啥想法