『学习笔记』浅谈莫比乌斯反演-526互联

莫比乌斯反演是数论中的重要内容。对于一些函数 $f(n)$，如果很难直接求出它的值，而容易求出其倍数和或约数和 $g(n)$，那么可以通过莫比乌斯反演简化运算，求得 $f(n)$ 的值。——OI-wiki

可见莫反的强大。

前置知识：数论分块

数论分块可以快速计算一些含有除法向下取整的和式，如 $\sum\limits_{i=1}^n f(i)\times g\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)$。由于 $y=\left\lfloor\dfrac nx\right\rfloor$ 的图像是成阶梯式的变化，便对于一段满足任意两个 $i,j$ 都满足 $\left\lfloor\dfrac ni\right\rfloor=\left\lfloor\dfrac nj\right\rfloor$的区间 $[l,r]$，其对应的答案为 $g\left(\left\lfloor\dfrac ni\right\rfloor\right)\times\sum\limits_{i=l}^rf(i)$，后面的便可以提前预处理出。

但是这个 $[l,r]$ 怎么求呢？

我们令 $k=\left\lfloor\dfrac nl\right\rfloor$，则有 $k\le\dfrac nl$。从而 $\left\lfloor\dfrac nk\right\rfloor\ge\left\lfloor\dfrac n{\frac nl}\right\rfloor=l$，得 $r\le\left\lfloor\frac n{\left\lfloor\frac nl\right\rfloor}\right\rfloor$，即 $r_{\max}=\left\lfloor\frac n{\left\lfloor\frac nl\right\rfloor}\right\rfloor$。

例题：UVa11526 H(n)

题意：求

\[\sum_{i=1}^n\left\lfloor\dfrac ni\right\rfloor \]

板子题，代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int n, ans = 0, l = 1;
  cin >> n;
  while(l <= n) {
    int r = n / (n / l);
    ans += (r - l + 1) * (n / l);
    l = r + 1;
  }
  cout << ans;
  return 0;
}

数论分块一般配合莫反进一步降低时间复杂度。

习题

定义

$\mu$ 为莫比乌斯函数，定义为

\[\mu(n)= \begin{cases} 1&n=1\\ 0&n\text{ 含有平方因子}\\ (-1)^k&k\text{ 为 }n\text{ 的本质不同质因子个数}\\ \end{cases} \]

令 $n=\prod\limits^k_{i=1}p_i^{c_i}$。

若 $n=1$，$\mu(n)=1$；
否则：
1. 若 $[c_i>1]\neq0$，则存在 $p_i^2\mid n $，此时 $\mu(n)=0$。
2. 否则每个质因子都只出现过一次，此时 $\mu(n)=(-1)^k$。

性质

首先，莫比乌斯函数为积性函数，并且满足

\[\sum\limits_{d\mid n}=\begin{cases} 1&n=1\\ 0&\text{else}\\ \end{cases} \]

接着给一下反演的结论：$[\gcd(i,j)=1]=\sum\limits_{d\mid\gcd(i,j)}\mu(d)$。

求法

因为莫比乌斯函数为积性函数，所以可用线性筛来求解。

代码如下：

inline void getMu() {
  mu[1] = 1;
  for(int i = 2; i <= n; ++i) {
    if(!vis[i]) {
      p[++tot] = i;
      mu[i] = -1;
    }
    for(int j = 1; j <= tot && i * p[j] <= n; ++j) {
      vis[i * p[j]] = 1;
      if(i % p[j] == 0) {
        mu[i * p[j]] = 0;
        break;
      }
      mu[i * p[j]] = -mu[i];
    }
  }
}

变换

令 $f(x),g(x)$ 为两个数论函数。

形式 $1$：若 $f(n)=\sum\limits_{d\mid n}g(d)$，则 $g(n)=\sum\limits_{d\mid n}\mu(d)f\left(\frac nd\right)$。

形式 $2$：若 $f(n)=\sum\limits_{n\mid d}g(d)$，则 $g(n)=\sum\limits_{n|d}\mu\left(\frac dn\right)f(d)$。

未完。