莫比乌斯反演

unravel_chess · 2023-05-12 20:27:08 · 个人记录

———— 非常感谢 newamnesia 热情帮助审核和排版，给予了很多知识上的指导

1.莫比乌斯函数的定义

如果将任意一个整数进行质因数分解：

x = p_1^{d_1}p_2^{d_2}p_3^{d_3}···p_n^{d_n}

那么就可以据此定义它的莫比乌斯函数：

0，\exists d_i>1\\ (-1)^n\\ \end{matrix}\right.

《蓝书》 上面的定义：

n = p_1^{d_1}p_2^{d_2}p_3^{d_3}···p_k^{d_k}

当n包含相等的质因子时候， \mu(n) = 0

当n的所有质因子个不相等的时候:

~~~~~~~$ 如果n有偶数个质因子，$\mu(n) = 1

~~~~~~~$ 如果n有奇数个质因子，$\mu(n) = -1

s(n) = \sum_{d | n}\mu(d)

计算n 的所有约数的莫比乌斯函数的和 s(n)
n = 1 , s(n) = \mu(1) = 1
n > 1, s(n) = 0

证明：

看因式分解
n = p_1^{d_1}p_2^{d_2}p_3^{d_3}···p_k^{d_k}
n > 1, 所以 k >= 1
定义 n 的约数 d, d = p_1^{a_1}p_2^{a_2}p_3^{a_3}···p_k^{a_k}, \space\space\space 0 <= a_i <= d_i
如果这个约数某一个次数是大于等于 2, 那就是 0，就不用考虑a_i >= 2 的情况了
那么就只需要计算 a_i == 0 || a_i == 1 的情况了。
最后莫比乌斯函数取决于p_1到p_k有多少个取1, 取的情况一共有k种

C_{K}^0(-1)^0 + C_{K}^1(-1)^1 +··· + C_{K}^k(-1)^k

然后使用二项式定理来计算
其实就是 (1 - 1)^k
和容斥原理的证明极为相似
证毕

2.莫比乌斯函数的定理

所谓反演就是反过来表示它：

若 F(n) = \sum_{d | n}f(d)

则 f(n) = \sum_{d | n} \mu(d)F(\frac{n}{d})

大部分题目可以直接套用这个定理，对于 F(n) 好求而 f(n) 不好求的时候。

证明：

\sum_{d | n} \mu(d) F(\frac{n}{d})

= \sum_{d | n}\mu(d) \sum_{i | \frac{n}{d}}f(i)

(d | n) ~\& ~(i | \frac{n}{d})~=>~(i | n)

因为当 d == 1 的时候， i 是可以取遍 n 的所有约数的。

那么就看有多少个 d 可以和 i 配对：

= \sum_{i | n} f(i) \sum_{d | n ~~ and ~~ i | \frac{n}{d}} \mu(d)

= \sum_{i | n} f(i) \sum_{d | \frac{n}{i}} \mu(d)

i | \frac{n}{d} \Leftrightarrow id | n \Leftrightarrow i | \frac{n}{d}

不难看出，后面的项是莫比乌斯函数的和，就是

$\frac{n}{i} == 1$时, $S(\frac{n}{i}) == 1

\frac{n}{i} > 1$ 时， $S(\frac{n}{i}) == 0

因此这一项只有当 i == n 的时候才不是 0 。

由此可以得到下面的式子：

= f(n)

到这里证明完毕。

题目中，一般会采用这个形式：

若 F(n) = \sum_{n | d}f(d) ，

则 f(n) = \sum_{n | d}\mu(\frac{d}{n})F(d)

## 证明： $$ \sum_{n | d}\mu(\frac{d}{n})F(d) $$ $$ = \sum_{n | d}\mu(\frac{d}{n}) \sum_{d | i}f(i) $$ - 这里的$i$ 也可以取遍 $n$ 的倍数在这里设 $d' = \frac{d}{n}

那么 d = d'n

就是说 i | d'n

也相当于 d'|\frac{i}{n}

从而得出：

\sum_{n | i}f(i)\sum_{d'|\frac{i}{n}}\mu(d')

右半边的和式其实就是上面提到的 S(\frac{i}{n}) 。
因此只有当 i == n 的时候才为 1, 其余时候都为 0 。

显然：

= f(n)

到这里证明完毕。

一个题目：Luogu Problem B

[HAOI2011]Problem b

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

2
2 5 1 5 1
1 5 1 5 2

样例输出 #1

14
3

提示

对于 100\% 的数据满足：1 \le n,k \le 5 \times 10^4，1 \le a \le b \le 5 \times 10^4，1 \le c \le d \le 5 \times 10^4。

解

这是一个容斥原理的思想，在最后统计结果的时候会用到

F(n) = \sum_{x = 1}^a \sum_{y = 1}^b[n | gcd(x, y)]

f(n) = \sum_{x = 1}^a \sum_{y = 1}^b [gcd(x, y) == n]

求f(k)
枚举n的倍数，枚举完:</font> F(n) = \sum_{n | d}f(d)
带入莫比乌斯反演定理，发现f(n)是可以使用公式来算的：

f(n) = \sum_{n | d}\mu(\frac{d}{n})F(d)

= \sum_{d | x \space and \space d|y}\mu(\frac{d}{n})F(d)

找 x 和 y 都是 d 的倍数的点，
有 \left\lfloor \frac{a}{d} \right\rfloor 个 x , 有 \left\lfloor \frac{b}{d} \right\rfloor 个y
任取一个 x 或者 y 都可以满足条件

F(n) = {\left\lfloor \frac{a}{d} \right\rfloor} {\left\lfloor \frac{b}{d} \right\rfloor}

f(n) = \sum_{n | d} \mu(\frac{d}{n}) {\left\lfloor \frac{a}{d} \right\rfloor} {\left\lfloor \frac{b}{d} \right\rfloor}

用d' 表示 \frac{d}{n}，因为更加直观。

= \sum_{d' > 0}\mu(d') {\left\lfloor \frac{a}{d'n} \right\rfloor} {\left\lfloor \frac{b}{d'n} \right\rfloor}

a' = \frac{a}{n} $ $ b' = \frac{b}{n}

= \sum_{d' > 0} \mu(d') {\left\lfloor \frac{a'}{d'} \right\rfloor} {\left\lfloor \frac{b'}{d'} \right\rfloor}

形如 \left\lfloor \frac{k}{x} \right\rfloor的东西, 当 x > k的时候一定是下取整的结果，只有O\sqrt{n}种取值
可以使用整数分块

一个公式

g(x) = \left\lfloor \frac{k}{\left\lfloor \frac{k}{x} \right\rfloor}\right\rfloor

这是和x相等的一段的最后一个点的值。
对于 a' 而言，有 O\sqrt{a'}个
对于 b' 而言，有 O\sqrt{b'}个
只需要从 1 看到 min(a', b') 就可以了

也就是说{\left\lfloor \frac{a'}{d'} \right\rfloor} {\left\lfloor \frac{b'}{d'} \right\rfloor}的值是相同的

让这个相同值为C

C \times (\mu(l)\space\mu(l + 1)\space\mu(l + 2) ···\space \mu(r))

可以发现这个是莫比乌斯函数的和。

先预处理一遍莫比乌斯函数的前缀和，

从而在 O(\sqrt{n}) 的复杂度之下得出答案 ,算下来差不多5e4\sqrt{5e4} \approx 1e7 一千多万吧。

很多莫比乌斯反演的题差不多都是这个过程。

二倍经验， Nice!

P3455 [POI2007]ZAP-Queries


#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5e5;

int prime[N], cnt, mu[N];
bool st[N];
int sum[N];
int T;
int a, b, c, d, k;

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

int g(int k, int x)
{
    return k / (k / x);
}

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

signed main()
{
    ios::sync_with_stdio(false);

    init();

    cin >> T;

    while (T--)
    {
        cin >> a >> b >> c >> d >> k;
        cout << f(b, d, k) - f(a - 1, d, k) - f(b, c - 1, k) + f(a - 1, c - 1, k) << "\n";
    }

    return 0;
}

类似应用了莫比乌斯反演的题目 Luogu P2398 GCD SUM

Next \space\space Question \space\space Luogu 约数个数和

题目要求

\sum_{i = 1}^N\sum_{j = 1}^Md(i * j)

转化一下 d(i*j) d(i * j) = \sum_{x | i}\sum_{y | j} [gcd(x, y) == 1]
这一步骤很难想滴。

解释这个转化：

可以去看Siyuan的博客，在后面有莫比乌斯函数对此的证明。

<!-- 考虑把每一个因子一一映射。

如果ij的因子k中有一个因子p_c，i中有因子p_a， &j&中有因子&p_b&。我们规定：

如果 c <= a，那么在i中选择。
如果 c > a，那么我们将c 减去 a ，在j 中选择 p^{c - a} （在 j 中选择 p^e 表示的是 p^{a + e}） -->

证明：

i = p_1^{d_1}p_2^{d_2}p_3^{d_3}···p_n^{d_n}

j = p_1^{a_1}p_2^{a_2}p_3^{a_3}···p_n^{a_n}

那这样：

约数个数： (d_1 + a_1 + 1)(d_2 + a_2 + 1) ···(d_k + a_k + 1)
然后取 p 的时候，不是x取p, \space y = 1, 就是翻过来的情况。

证明完毕。

\sum_{i = 1}^N\sum_{j = 1}^M\sum_{x | i}\sum_{y | j}[gcd(x, y) == 1]

设：

F(n) = \sum_{i = 1}^N\sum_{j = 1}^M\sum_{x | i}\sum_{y | j}[x | gcd(x, y)]

f(n) = \sum_{i = 1}^N\sum_{j = 1}^M\sum_{x | i}\sum_{y | j}[gcd(x, y) == n]

则：

F(n) = \sum_{n | d}f(d)

所以：

f(n) = \sum_{n | d}\mu(\frac{d}{n})F(d)

f(1) = \sum_{d = 1}^N\mu(d)F(d)

考虑 F(d) 怎么求：

F(n) = \sum_{x = 1}^N\sum_{y = 1}^M\left\lfloor \frac{N}{x} \right\rfloor \left\lfloor \frac{M}{y} \right\rfloor [n | gcd(x, y)]

设：

x' = \frac{x}{n}, y' = \frac{y}{n}

那么：

= \sum_{x' = 1}^{\frac{N}{n}}\sum_{y' = 1}^{\frac{M}{n}} \left\lfloor \frac{N}{nx'} \right\rfloor \left\lfloor\frac{M}{ny'}\right\rfloor

设：

N' = \frac{N}{n}, M' = \frac{M}{n}

i = x', j = y'

有：

= \sum_{i = 1}^{N'}\sum_{j = 1}^{M'}\left\lfloor\frac{N'}{i}\right\rfloor \left\lfloor \frac{M'}{j} \right\rfloor

= \sum_{i = 1}^{N'}\left\lfloor\frac{N'}{i}\right\rfloor\sum_{j = 1}^{M'}\left\lfloor \frac{M'}{j} \right\rfloor

令：

H(k) = \sum_{i = 1}^k \left\lfloor \frac{k}{i}\right\rfloor

则：

= H(N') * H(M')

f(1) = \sum_{d = 1}^N\mu(d)H(\frac{N}{d}) H(\frac{M}{d})

tips:$ 这是到 $ min(N, M)
这个 H(x) 是可以先预处理的，然后这玩意又得分块去做
再预处理一遍前缀和，利用和上面那个题目类似的方法去分块, 大概有O(\sqrt{max(n ,m)})块，每一块的左右端点也是可以用g(x) 知道的。
总的来说，使用了两次分块

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 10;
int T;
int n, m;
int prime[N], cnt, mu[N];
int sum[N], h[N];
bool st[N];
int g(int k, int x)
{
    return k / (k / x);
}
void init()
{
    mu[1] = 1;
    for (int i = 2; i <= N; i++)
    {
        if (!st[i])
        {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; prime[j] * i <= N; j++)
        {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0)
                break;
            mu[prime[j] * i] = -mu[i];
        }
    }
    for (int i = 1; i <= N; i++)
        sum[i] = sum[i - 1] + mu[i];
    for (int i = 1; i <= N; i++)
    {
        for (int l = 1, r; l <= i; l = r + 1)
        {
            r = min(i, g(i, l));
            h[i] += (r - l + 1) * (i / l);
        }
    }
    return;
}
signed main()
{
    init();
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        int res = 0;
        int k = min(n, m);
        for (int l = 1, r; l <= k; l = r + 1)
        {
            r = min(k, min(g(n, l), g(m, l)));
            res += (sum[r] - sum[l - 1]) * h[n / l] * h[m / l];
        }
        cout << res << endl;
    }
    return 0;
}

对前面的一个补充结论：

\sum_{d | n}\mu(d) == [n = 1]

[gcd(i,j) == 1] = \sum_{d|gcd(i, j)} \mu(d) = \sum_{d | i, d | j} \mu(d)

这个东西很重要，是莫比乌斯函数最常用的了。
[n==1]$表示只有当$n=1$成立时，返回值为$1$；否则返回值为$0

说白了，就是那个s(n)函数啦