铃悬的数学小讲堂——狄利克雷卷积与莫比乌斯反演

符号及规定

1. $[P]$ 是指，当 $P$ 为真时，式子的值是 $1$ ；当 $P$ 为假时，式子的值是 $0$ 。// 可以理解成， P 是一个 0/1 布尔值， $[P]$ 就是 (int)P。
2. $a\mid b$ 是指 $b$ 被 $a$ 整除，即存在一个整数 $k$ 使得 $b=ka$ ；$n\perp m$ 是指 $n$ 与 $m$ 互质（注意，$1\perp1$ 是成立的）。
3. 数论函数（见下）用小写粗体字母或普通希腊文字母（如 $\mathbf{f,g,h},\mu,\epsilon$ ）表示。// QAQ希腊文字母不能粗体

数论函数 & 狄利克雷卷积

1. 交换律 $\mathbf f\ast\mathbf g=\mathbf g\ast\mathbf f$ ；// 这个结论还是很简单哒
2. 结合律 $(\mathbf f\ast\mathbf g)\ast\mathbf h=\mathbf f\ast(\mathbf g\ast\mathbf h)$。这是因为
   $\sum_{(i\cdot j)\cdot k=n}\left(\mathbf f(i)\mathbf g(j)\right)\mathbf h(k)=\sum_{i\cdot(j\cdot k)=n}\mathbf f(i)\left(\mathbf g(j)\mathbf h(k)\right)$
   由此，我们以后不再区分 $(\mathbf f\ast\mathbf g)\ast\mathbf h=\mathbf f\ast(\mathbf g\ast\mathbf h)$ ，并将其写为 $\mathbf f\ast\mathbf g\ast\mathbf h$ ；
3. 分配律 $(\mathbf f+\mathbf g)\ast \mathbf h=\mathbf f\ast\mathbf h+\mathbf g\ast\mathbf h$ ；// 留作习题 读者自证（
4. 不知道叫什么 $(x\mathbf f)\ast\mathbf g=x(\mathbf f\ast\mathbf g)$ // 同上
5. 单位元 $\epsilon\ast\mathbf f=\mathbf f$ ，其中 $\epsilon(n)=[n=1]=\begin{cases}1&n=1\\0&n>1\end{cases}$ ；//同上，这三个结论都可以直接套定义得到
6. 逆元 对每个 $\mathbf f(1)\neq0$ 的函数 $\mathbf f$ ，都存在一个函数 $\mathbf g$ 使得 $\mathbf f\ast\mathbf g=\epsilon$ 。

积性函数

1. $nm=1$ 时， $\mathbf g(1)=1$ ，结论显然成立；
2. 假设 $nm > 1$ ，当 $n'm'<nm$ 的时候有 $\mathbf g(n'm')=\mathbf g(n')\mathbf g(m')$ ，
   $\begin{aligned}\mathbf g(nm)&=-\sum_{d\mid nm,d\neq1}\mathbf f(d)\mathbf g\left(\frac{nm}d\right)\\&=-\sum_{a\mid n,b\mid m,ab\neq1}\mathbf f(ab)\mathbf g\left(\frac{nm}{ab}\right)\\&=-\sum_{a\mid n,b\mid m,ab\neq1}\mathbf f(a)\mathbf f(b)\mathbf g\left(\frac na\right)\mathbf g\left(\frac mb\right)\\&=\mathbf f(1)\mathbf f(1)\mathbf g(n)\mathbf g(m)-\sum_{a\mid n,b\mid m}\mathbf f(a)\mathbf f(b)\mathbf g\left(\frac na\right)\mathbf g\left(\frac mb\right)\\&=\mathbf g(n)\mathbf g(m)-\left(\sum_{a\mid n}\mathbf f(a)\mathbf g\left(\frac na\right)\right)\left(\sum_{b\mid m}\mathbf f(b)\mathbf g\left(\frac mb\right)\right)\\&=\mathbf g(n)\mathbf g(m)-\epsilon(n)\epsilon(m)\\&=\mathbf g(n)\mathbf g(m)\end{aligned}$

莫比乌斯反演

例题

P2257 YY 的 GCD

题意

解法

for (int j = 0; j < prime_count; j++)
  for (int p = prime[j], i = 1; i * p <= N; i++)
    g[i * p] += mu[i];

简单题

题意

解法

难题

题意

解法

void get_g_1(int N, const int *f, int *g) {
  for (int i = 1; i <= N; i++) g[i] = 0;
  for (int i = 1; i <= N; i++)
    for (int j = 1; i * j <= N; j++)
      g[i * j] = (g[i * j] + mu[i] * f[j]) % mod;
} // 依照定义，O(nlogn)

void get_g_2(int N, const int *f, int *g) {
  for (int i = 1; i <= N; i++) g[i] = f[i];
  for (int i = 1; i <= N; i++)
    for (int j = 2; i * j <= N; j++)
      g[i * j] = (g[i * j] - g[i]) % mod;
} // 类似求狄利克雷卷积逆的方式，不需要线性筛 mu ，O(nlogn)

void get_g_3(int N, const int *f, int *g) {
  for (int i = 1; i <= N; i++) g[i] = f[i];
  for (int i = 0; i < prime_count; i++)
    for (int j = N / prime[i]; j >= 1; j--)
      g[j * prime[i]] = (g[j * prime[i]] - g[j]) % mod;
} // Magic! O(nloglogn)

小结