数论进阶——莫比乌斯反演

博主： spirit
发布时间：2021 年 03 月 27 日
3822 次浏览
暂无评论
2681字数
分类：数论

# 数论进阶——莫比乌斯反演

> 莫比乌斯反演是数论中的重要内容。对于一些函数 $f(n)$，如果很难直接求出它的值，而容易求出其倍数和或约数和 $g(n)$，那么可以通过莫比乌斯反演简化运算，求得 $f(n)$ 的值。
> 
> 开始学习莫比乌斯反演前，我们需要一些前置知识：**积性函数**、**Dirichlet 卷积**、**莫比乌斯函数**。
> 
> ——引用自 [OI Wiki - 莫比乌斯反演](https://oi-wiki.org/math/mobius/)

## 一、莫比乌斯函数

- 定义：假设 $x = p_1^{a_1} \cdot p_2^{a_2} \cdot p_3^{a_3} ... p_k^{a_k}$ ，则莫比乌斯函数 $\mu(x)$ 的取值分为两种情况：
  
  $$
  \mu(x) = 
  \begin{cases} 
  0, \quad & {\exists a_i \geq 2}\\
  (-1)^k, \quad & {\forall a_i \leq 1}\\
  \end{cases}
  $$
- 快速计算：利用素数筛的思想，线性时间求 $[1, n]$ 的 $\mu(x)$ 值。
  
  ```cpp
  void get_mobius(int n) {
      mobius[1] = 1;
      for (int i = 2; i <= n; i++) {
          if (!prime[i]) {
              primes[cnt++] = i;
              mobius[i] = -1;
          }
          for (int j = 0; primes[j] <= n / i; j++) {
              int t = i * primes[j];
              prime[t] = true;
              if (i % primes[j] == 0) {
                  mobius[t] = 0;
                  break;
              }
              mobius[t] = -1 * mobius[i];
          }
      }
  }
  ```
- 定义 $S(n)$ 为 $n$ 的所有约数的莫比乌斯函数的和。则 $S(n)$ 的取值情况如下：
  
  $$
  S(n) = 
  \begin{cases}
  1, \quad & n = 1\\
  0, \quad & n > 1\\
  \end{cases}
  $$
  
  证明：设 $n = p_1^{a_1} \cdot p_2^{a_2} \cdot p_3^{a_3} ... p_k^{a_k}$ ，我们枚举 $n$ 的所有约数，若某个约数 $d$ 的质因数分解中某个质因子的幂大于 $1$ ，则 $\mu(d) = 0$ ，这些约数我们可以直接忽略。对于剩下的约数来说，他们的和可以写成：
  
  $$
  \begin{equation}\begin{split}
  &S(n) = C_k^0(-1)^0 + C_k^1(-1)^1 + \ ... \ + C_k^k(-1)^k\\
  &= C_k^0(-1)^01^k + C_k^1(-1)^11^{k-1} + \ ... \ + C_k^k(-1)^k1^0\\
  &= (-1 + 1)^k\\
  \end{split}\end{equation}
  $$
  
  显然只有当 $n = 1$ ，$k = 0$ 时，$S(n) = 1$ ，其他情况均有 $S(n) = 0$ 。

## 二、莫比乌斯反演

### 形式一

- 若 $F(n) = \sum_{d | n} f(d)$ ，则 $f(n) = \sum_{d | n} \mu(d) F(\frac{n}{d})$ 。
- 证明：
  
  $$
  \begin{equation}\begin{split}
  &\sum_{d|n} \mu(d) F(\frac{n}{d})\\
  &= \sum_{d|n} (\mu(d) \sum_{d'|\frac{n}{d}} f(d'))\\
  &= \sum_{d'|n} (f(d') \sum_{d | \frac{n}{d'}} \mu(d))\\
  &= \sum_{d'|n} (f(d') S(\frac{n}{d'}))\\
  &= f(n)\\
  \end{split}\end{equation}
  $$

### 形式二（常用）

- 若 $F(n) = \sum_{n | d} f(d)$ ，则 $f(n) = \sum_{n | d} \mu(\frac{d}{n}) F(d)$ 。
- 证明：
  
  $$
  \begin{equation}\begin{split}
  &\sum_{n | d} \mu(\frac{d}{n}) F(d)\\
  &= \sum_{n | d} (\mu(\frac{d}{n}) \sum_{d | d'} f(d'))\\
  &= \sum_{n | d'} (f(d') \sum_{\frac{d}{n} | \frac{d'}{n}} \mu(\frac{d}{n}))\\
  &= \sum_{n | d'} (f(d') S(\frac{d'}{n}))\\
  &= f(n)\\
  \end{split}\end{equation}
  $$

## 例题

> 对于给出的 $n$ 个询问，每次求有多少个数对 $(x,y)$ ，满足 $a≤x≤b，c≤y≤d$，且 $gcd(x,y)=k$，$gcd(x,y)$ 函数为 $x$ 和 $y$ 的最大公约数。

**输入格式**

> 第一行一个整数 $n$。
> 
> 接下来 $n$ 行每行五个整数，分别表示 $a、b、c、d、k$。

**输出格式**

> 共 $n$ 行，每行一个整数表示满足要求的数对 $(x,y)$ 的个数。

**数据范围**

> $1 \le n \le 50000$
> 
> $1 \le a \le b \le 50000$
> 
> $1 \le c \le d \le 50000$
> 
> $1 \le k \le 50000$

**输入样例：**

```
2
2 5 1 5 1
1 5 1 5 2
```

**输出样例：**

```
14
3
```

### 思路分析

直接去求答案是比较困难的，这里利用差分和前缀和的思想，定义一个函数 $f(a, b, k)$ 求对于 $1 \leq x \leq a, 1\leq y \leq b$ ，满足 $gcd(x, y) = k$ 的 $(x, y)$ 的对数。接下来考虑如何求 $f(a, b, k)$ （后面简称为 $f(k)$ ）的问题。

接下来利用莫比乌斯反演求 $f(k)$ 函数。定义函数 $F(k) = \sum_{k | d} f(d)$ ，即求所有最大公约数是 $k$ 的倍数的 $(x, y)$ 的对数。显然这个函数是很好求的，只要满足 $x$ 和 $y$ 都是 $k$ 的倍数就可以了，即 $F(x) = \lfloor \frac{x}{k} \rfloor \lfloor \frac{y}{k} \rfloor$ 。然后套用莫比乌斯反演公式得到 $f(k) = \sum_{k | d} \mu(\frac{d}{k}) F(d)$ ，令 $d' = \frac{d}{k}$ ，$x' = \frac{x}{k}$ ，$y' = \frac{y}{k}$ ，则 $f(k) = \sum \mu(d') \lfloor \frac{x'}{d'} \rfloor \lfloor \frac{y'}{d'} \rfloor$ 。这时的式子看起来就好求多了，但是直接求解的时间复杂度为 $O(n)$ ，考虑到多组数据，还需要进一步优化。

### 数论分块

在上面的式子中，有一部分形如 $\lfloor \frac{n}{i} \rfloor$ 的式子。由于是向下取整，这个式子在一个连续区间内的取值有可能是相等的，如果对于一个整数 $i$ ，可以快速求出满足 $\lfloor \frac{n}{i} \rfloor = \lfloor \frac{n}{j} \rfloor$ 的最大整数 $j$ ，就能够在 $O(1)$ 的时间算出一段区间的取值，将求解上一问题的时间复杂度降低到 $O(\sqrt(n))$ ，整数 $j$ 的取值应该为 $\lfloor \frac{n}{\frac{n}{i}} \rfloor$ 。

- 时间复杂度证明：$i$ 的取值范围为 $[1, n]$ ，我们以 $i = \sqrt(n)$ 为分界线，对于区间 $[1, \sqrt(n)]$ ，显然这部分最多只有 $\sqrt(n)$ 种取值；对于区间 $[\sqrt(n), n]$ ，这部分的 $\lfloor \frac{n}{i} \rfloor$ 取值都应小于等于 $\frac{n}{\sqrt(n)} = \sqrt(n)$ ，最多也只有 $\sqrt(n)$ 种取值，即最多有 $2 \sqrt(n)$ 分块的区间，时间复杂度自然为 $O(\sqrt(n))$ 。
- $j$ 的取值证明可以参考[OI-Wiki](https://oi-wiki.org/math/mobius/#_3) ![](https://i.loli.net/2021/03/27/TCsRWdiS75y6Agh.png)

### 代码实现

```cpp
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;
typedef long long LL;
const int N = 5e4 + 10;
int primes[N], cnt, mu[N], sum[N];
bool prime[N];

void init(int n) {
    mu[1] = sum[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!prime[i]) primes[cnt++] = i, mu[i] = -1;
        for (int j = 0; primes[j] <= n / i; j++) {
            prime[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
            mu[i * primes[j]] = mu[i] * -1;
        }
        sum[i] = sum[i - 1] + mu[i];
    }
}

LL f(int a, int b, int k) {
    a /= k, b /= k;
    int m = min(a, b);
    LL res = 0;
    for (int l = 1, r; l <= m; l = r + 1) {
        r = min(m, min(a / (a / l), b / (b / l)));
        res += (LL)(a / l) * (b / l) * (sum[r] - sum[l - 1]);
    }
    return res;
}

int main() {
    init(50000);
    int n, a, b, c, d, k;
    cin >> n;
    while (n--) {
        scanf("%d %d %d %d %d", &a, &b, &c, &d, &k);
        LL res =
            f(b, d, k) - f(a - 1, d, k) - f(b, c - 1, k) + f(a - 1, c - 1, k);
        printf("%lld\n", res);
    }
    return 0;
}
```

最后修改：2021 年 03 月 28 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

数论进阶——莫比乌斯反演

spirit • 2021 年 03 月 27 日

# 数论进阶——莫比乌斯反演

## 一、莫比乌斯函数

## 二、莫比乌斯反演

### 形式一

### 形式二（常用）

## 例题

> 对于给出的 $n$ 个询问，每次求有多少个数对 $(x,y)$ ，满足 $a≤x≤b，c≤y≤d$，且 $gcd(x,y)=k$，$gcd(x,y)$ 函数为 $x$ 和 $y$ 的最大公约数。

**输入格式**

> 第一行一个整数 $n$。
> 
> 接下来 $n$ 行每行五个整数，分别表示 $a、b、c、d、k$。

**输出格式**

> 共 $n$ 行，每行一个整数表示满足要求的数对 $(x,y)$ 的个数。

**数据范围**

> $1 \le n \le 50000$
> 
> $1 \le a \le b \le 50000$
> 
> $1 \le c \le d \le 50000$
> 
> $1 \le k \le 50000$

**输入样例：**

```
2
2 5 1 5 1
1 5 1 5 2
```

**输出样例：**

```
14
3
```

### 思路分析

### 数论分块

### 代码实现

```cpp
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;
typedef long long LL;
const int N = 5e4 + 10;
int primes[N], cnt, mu[N], sum[N];
bool prime[N];

数论进阶——莫比乌斯反演

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Kattis Message （状态机模型 + 矩阵快速幂）

数论进阶——莫比乌斯反演

Codeforces Round #703 (Div. 2)

SDUT 2021 Winter Individual Contest - E

Kattis Fruit Slicer （计算几何 + 扫描线）

SDUT 2021 Winter Individual Contest - E

SDUT 2021 Winter Individual Contest - G

SDUT 2020 Autumn Team Contest---44

线性DP入门

Windows Terminal & PowerShell 美化记录

数论进阶——莫比乌斯反演

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

数论进阶——莫比乌斯反演

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款