莫比乌斯反演

一个小题

先讲一个同学出的题了解一下一种数论变换方式
给定 $n(n\leq 10^6)$ ,求
$$ \prod_{i=1}^{n}\prod_{j=1}^{n}\frac{lcm(i,j)}{gcd(i,j)} $$
虽然有 $\mathcal{O(n)}$ 的方法,但是这里不提了
考虑式子化简
$$\prod_{i=1}^{n}\prod_{j=1}^{n}\frac{lcm(i,j)}{gcd(i,j)}$$
$$ =\prod_{i=1}^{n}\prod_{j=1}^{n}\frac{i\cdot j}{gcd^2(i,j)}=\frac{\prod_{i=1}^{n}\prod_{j=1}^{n}i\cdot j}{\prod_{i=1}^{n}\prod_{j=1}^{n}gcd^2(i,j)} $$
上面很好处理,于是考虑下面怎么求

设 $f(n)=\prod_{i=1}^{n}\prod_{j=1}^{n}gcd^2(i,j)$ ,变换为枚举最大公因数,则
$$ f(n)=\prod_{d=1}^{n}d^{2\sum_{i=1}^{n}\sum_{j=1}^{n}[(i,j)==d]} $$
设 $g(d) = 2\sum_{i=1}^{n}\sum_{j=1}^{n}[(i,j)==d]$ ,再次变换为枚举最大公因数,则
$$ g(d)=2\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[(i,j)==1] $$
此时可以变换一下就可以用预处理欧拉函数的方法在 $\mathcal{O(1)}$ 的时间内得出 $g(d)$
通过上面的变换可以发现将式子转化,将不好枚举,不好计算的东西转化为好枚举的可以起到优化的作用,还可以发现通过组合意义进行变换是一个不错的方式

狄利克雷卷积

对于两个数论函数 $f,g$ 定义它们的狄利克雷卷积
$$ (f * g)(n) = \sum_{d|n}f(d)g(\frac{n}{d}) $$
满足的三个性质:

结合律

即 $(f * g) * h=f * (g * h)$
证明:
$$ (f * g) * h \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
$$ \ \ = \sum_{d_1|n}(\sum_{d_2|d_1}f(d_2)\cdot g(\frac{d_1}{d_2}))h(\frac{n}{d_1}) $$
$$\ \ =\sum_{d_2|n}f(d_2)\sum_{d_2|d_1,d_1|n}g(\frac{d_1}{d_2})h(\frac{n}{d_1}) $$
$$=\sum_{d_2|n}f(d_2)\sum_{k|\frac{n}{d_2}}g(k)\cdot h(\frac{n}{d_2 k}) $$
$$ =f * (g * h) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$

交换律

积性函数性质不变

即:若 $f,g$ 为积性函数,则 $f * g$ 为积性函数
证明:
$$(f * g)(n)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
$$ =\sum_{d_1|u, d_2|v}^{u\cdot v = n} f(d_1 d_2)\cdot g(\frac{uv}{d_1 d_2}) \ \ $$
$$\ \ \ \ \ \ \ \ \ \ \ \ = \sum_{d_1|u,d_2|v} f(d_1)\cdot f(d_2)\cdot g(\frac{u}{d_1})\cdot g(\frac{v}{d_2}) $$
$$\ \ \ \ \ \ \ \ = \sum_{d_1|u}f(d_1)\cdot g(\frac{u}{d_1})\sum_{d_2|v}f(d_2)\cdot g(\frac{v}{d_2}) $$
$$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = (f * g)(u)\cdot (f * g)(v)\ \ \ \ (u\cdot v=n,(u,v)=1) $$

特殊数论函数

  1. $\mu$ 莫比乌斯函数
  2. 单位元 $\epsilon(n)=[n=1]$
  3. $I_k (n)=n^k \ \ \ \ \ \ (\mu * I_0=\epsilon)$

莫比乌斯函数

选区_104.png
可以使用线性筛以 $\mathcal{O(n)}$ 的复杂度得到 $\mu$

for (int i = 2; i < N; ++i) {
        if (isPrime[i]) primes[++num] = i, mu[i] = -1;
        for (int j = 1; j <= num; ++j) {
            if (primes[j] * i > N)
                break;
            isPrime[primes[j] * i] = false;
            if (i % primes[j] == 0) {
                mu[primes[j] * i] = 0;
                break;
            } else mu[primes[j] * i] = -mu[i];
        }
    }

性质

性质一

莫比乌斯函数是积性函数
$$ \mu(a)\mu(b)=\mu(ab) \ \ \ \ \ \ ((a,b)=1) $$

性质二

$$\color{red}{[n=1]=\varepsilon (n)=\sum_{d|n}\mu(d)}$$
其中
$$
\varepsilon(n)=\begin{cases} 1 &n=1\\ 0 &n\neq 1\end{cases}
$$
这个性质还是挺有用的

补充性质

实际上就是性质二,但是由于用的十分广泛,所以单独拿出来讲一下
$$ [gcd(i,j)=1]=\sum_{d\mid gcd(i,j)}\mu(d) $$

扩展

$$
\begin{eqnarray}
\sum_{d\mid n}\varphi(d)&=&n\\
\sum_{d\mid n} d\mu(\frac{n}{d})&=&\varphi(n)
\end{eqnarray}
$$

总结

很多时候是莫比乌斯函数的性质二(或补充性质)成为化简式子的关键之一,相对起来并不一定是莫比乌斯反演最重要

莫比乌斯反演

对于 $f(n),g(n)$ 两个数论函数
若有
$$f(n)=\sum_{d\mid n} g(d) $$
则有
$$ g(n)=\sum_{d\mid n}\mu(d)f(\frac{n}{d}) $$

例题

在这篇博客里写了

引用资料

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注