莫比乌斯反演-笔记

关于莫比乌斯反演,主要摘自策爷的笔记知乎–如何证明莫比乌斯反演

Dirichlet卷积定义:对于数论函数$f$和$g$,他们的卷积为$f*g$为

$$(f*g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d})$$


定义以下函数:

衡为1的常函数$1(n)=1$

恒等函数$id(n)=n$

单位函数$\epsilon(n)=[n=1]$


定义莫比乌斯函数:

当$n=1$时,$\mu(1)=1$。

否则将$n$分解成$p_1^{a_1}p_2^{a_2}…p_k^{a_k}$这样的形式,$p_i$为质数,且$a_i$均为$1$时,则$\mu(n)=(-1)^k$。

其余情况$\mu(n)=0$


可以得到:

$$1*\mu=\sum_{d\mid n}\mu(d)=\epsilon(n)$$

由二项式定理可证,这个用途在于当存在类似$ \epsilon(gcd(i,j))$这样的函数的时候,可转换成$\sum_{d\mid n}\mu(d)$的形式,用于进一步变换。

而且证明莫比乌斯反演时,这是一个关键步骤。


莫比乌斯反演:

$$F(n)=\sum_{d\mid n}f(d) \Rightarrow f(n)=\sum_{d\mid n}\mu(d)F(n/d)$$

其实也可以写成Dirichlet卷积的形势:$F=1*f$,这样更好证明。

$$F=1f \Rightarrow \muF=\mu1f \Rightarrow \mu*F=f$$


然后其实莫比乌斯反演还有另外一种形式:

$$F(n)=\sum_{n\mid d}f(d) \Rightarrow f(n)=\sum_{n\mid d}\mu(\frac{d}{n})F(d)$$

证明:

$$\sum_{n\mid d}\mu(\frac{d}{n})F(d) = \sum_{n\mid d}\mu(\frac{d}{n})\sum_{d\mid m}f(m) =\sum_{n\mid m}f(m)\sum_{d\mid \frac{m}{n}}\mu(d)$$

显然当且仅当$m=n$时$\sum_{d\mid \frac{m}{n}}\mu(d)=1$其余为$0$,所以

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


例题:3529: [Sdoi2014]数表

大意:$Q$个询问,每个询问给出$n,m,a$。有一张$nm$的网格,每个格子$(i,j)$的数字为$gcd(i,j)$的约数和。问格子上的数字小于$a$的数字的和,可离线。$ Q \le 210^4 ,1 \le n,m \le 10^5, a\le10^9$

题解(参考PoPoQQQ的题解):

约定$n \le m$,否则交换即可,不影响解。

用$g(k)$表示网格中数字为$k$的数量,记$n’=\lfloor\frac{n}{k}\rfloor$。

$$\begin{split} g(k) =\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k] =\sum_{i=1}^{n’}\sum_{j=1}^{m’}[gcd(i,j)=1] =\sum_{i=1}^{n’}\sum_{j=1}^{m’}\sum_{d\mid gcd(i,j)}\mu(d)=\sum_{d=1}^{n’}\mu(d)\lfloor\frac{n’}{d}\rfloor\lfloor\frac{m’}{d}\rfloor \end{split} $$

用$f(k)$表示$k$的约数和,枚举每个数的倍数可在$O(nlogn)$时间预处理。

那么显然没有a的限制时

$$ \begin{split} ans=\sum_{k=1}^{n}f(k)g(k)= \sum_{k=1}^{n}f(k)\sum_{d=1}^{n’}\mu(d)\lfloor\frac{n’}{d}\rfloor\lfloor\frac{m’}{d}\rfloor=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{k\mid T}f(k)\mu(\frac{T}{k}) \ \end{split} $$

对于最后一步变换是把$T$替换成$dk$。因为$\lfloor\frac{n}{T}\rfloor$最多有$2\sqrt{n}$种结果,记$h(T)=\sum_{k\mid T}f(k)\mu(\frac{T}{k})$,那么预处理出$h$的前缀和就可以在$O(\sqrt{n})$的时间完成一次询问。

因为存在a的限制,所以可以先给询问按照a排序,然后离线处理。对于每个询问,我们把$k \le a$的插入$h$中,因为需要插入,所以$h$用树状数组来维护。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int L_N = 1e5 + 10;
int mu[L_N], pr[L_N], pn, not_p[L_N];
struct F
{
int val, id;
bool operator<(const F &f) const
{
return val < f.val;
}
} f[L_N];
struct Query
{
int n, m, a, id;
bool operator<(const Query &q) const
{
return a < q.a;
}
} qs[L_N];
struct TreeArr
{
int a[L_N];
int lowbit(int i) { return i & -i; }
void add(int p, int val)
{
for (; p < L_N; p += lowbit(p))
{
a[p] += val;
}
}
int query(int p)
{
int ret = 0;
for (; p; p -= lowbit(p))
{
ret += a[p];
}
return ret;
}
int query(int l, int r)
{
return query(r) - query(l - 1);
}
} ta;
void pre()
{
mu[1] = 1;
for (int i = 2; i < L_N; i++)
{
if (!not_p[i])
mu[i] = -1, pr[++pn] = i;
for (int j = 1; j <= pn && ipr[j] < L_N; j++)
{
not_p[pr[j] i] = true;
if (i % pr[j] == 0)
{
mu[pr[j] i] = 0;
break;
}
mu[pr[j] i] = -mu[i];
}
}

for (int i = 1; i < L_N; i++)
{
f[i].id = i;
for (int j = i; j < L_N; j += i)
{
f[j].val += i;
}
}
sort(f + 1, f + L_N);
}

void insert(F f)
{
for (int j = f.id; j < L_N; j += f.id)
{
ta.add(j, f.valmu[j / f.id]);
}
}

int sol(int n, int m)
{
if (n > m)
swap(n, m);
int ed = 0, ret = 0;
for (int t = 1; t <= n; t = ed + 1)
{
ed = min(n / (n / t), m / (m / t));
ret += (n / t)(m / t) * ta.query(t, ed);
}
return ret;
}

int ANS[L_N];
int main()
{
//freopen(“in.txt”,”r”,stdin);

pre();

int T;
scanf(“% d”, &T);
for (int i = 1; i <= T; i++)
{
scanf(“% d % d % d”, &qs[i].n, &qs[i].m, &qs[i].a);
qs[i].id = i;
}
sort(qs + 1, qs + 1 + T);

int fn = 1;
for (int i = 1; i <= T; i++)
{
Query &q = qs[i];
while (fn < L_N && f[fn].val <= q.a)
{
insert(f[fn]);
fn++;
}
ANS[q.id] = sol(q.n, q.m);
}

for (int i = 1; i <= T; i++)
{
ANS[i] &= (1 << 31) - 1;
printf(“% d\n“, ANS[i]);
}

return 0;
}