莫比乌斯反演

简介

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

开始学习莫比乌斯反演前,我们需要一些前置知识: 积性函数Dirichlet 卷积莫比乌斯函数


前置知识

引理 1

\forall a,b,c\in\mathbb{Z},\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor

略证:

\begin{split} &\frac{a}{b}=\left\lfloor\frac{a}{b}\right\rfloor+r(0\leq r<1)\\ \implies &\left\lfloor\frac{a}{bc}\right\rfloor =\left\lfloor\frac{a}{b}\cdot\frac{1}{c}\right\rfloor =\left\lfloor \frac{1}{c}\left(\left\lfloor\frac{a}{b}\right\rfloor+r\right)\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c} +\frac{r}{c}\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor\\ &&\square \end{split}

引理 2

\forall n \in N, \left|\left\{ \lfloor \frac{n}{d} \rfloor \mid d \in N \right\}\right| \leq \lfloor 2\sqrt{n} \rfloor

|V| 表示集合 V 的元素个数

略证:

对于 d\leq \left\lfloor\sqrt{n}\right\rfloor \left\lfloor\frac{n}{d}\right\rfloor \left\lfloor\sqrt{n}\right\rfloor 种取值

对于 d> \left\lfloor\sqrt{n}\right\rfloor ,有 \left\lfloor\frac{n}{d}\right\rfloor\leq\left\lfloor\sqrt{n}\right\rfloor ,也只有 \left\lfloor\sqrt{n}\right\rfloor 种取值

综上,得证

数论分块

数论分块的过程大概如下:考虑含有 \left\lfloor\frac{n}{i}\right\rfloor 的求和式子( n 为常数)

对于任意一个 i(i\leq n) ,我们需要找到一个最大的 j(i\leq j\leq n) ,使得 \left\lfloor\frac{n}{i}\right\rfloor = \left\lfloor\frac{n}{j}\right\rfloor .

j=\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor .

略证:

\begin{split} &\left\lfloor\frac{n}{i}\right\rfloor \leq \frac{n}{i}\\ \implies &\left\lfloor\frac{n}{ \left\lfloor\frac{n}{i}\right\rfloor }\right\rfloor \geq \left\lfloor\frac{n}{ \frac{n}{i} }\right\rfloor = \left\lfloor i \right\rfloor=i \\ \implies &i\leq \left\lfloor\frac{n}{ \left\lfloor\frac{n}{i}\right\rfloor }\right\rfloor\\ &&\square \end{split}

j=\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor .

利用上述结论,我们每次以 [i,j] 为一块,分块求和即可


积性函数

定义

\gcd(x,y)=1 f(xy)=f(x)f(y) ,则 f(n) 为积性函数。

性质

f(x) g(x) 均为积性函数,则以下函数也为积性函数:

\begin{aligned} h(x)&=f(x^p)\\ h(x)&=f^p(x)\\ h(x)&=f(x)g(x)\\ h(x)&=\sum_{d\mid x}f(d)g(\frac{x}{d}) \end{aligned}

例子

  • 单位函数: \epsilon(n)=[n=1]
  • 恒等函数: \operatorname{id}_k(n)=n^k \operatorname{id}_{1}(n) 通常简记作 \operatorname{id}(n)
  • 常数函数: 1(n)=1
  • 除数函数: \sigma_{k}(n)=\sum_{d\mid n}d^{k} \sigma_{0}(n) 通常简记作 \operatorname{d}(n) \tau(n) \sigma_{1}(n) 通常简记作 \sigma(n)
  • 欧拉函数: \varphi(n)=\sum_{i=1}^n [\gcd(i,n)=1]
  • 莫比乌斯函数: \mu(n) = \begin{cases}1 & n=1 \\ 0 & \exists d>1:d^{2} \mid n \\ (-1)^{\omega(n)} & otherwise\end{cases} 其中 \omega(n) 表示 n 的本质不同质因子个数,是一个积性函数。

Dirichlet 卷积

定义

定义两个数论函数 f,g 的 Dirichlet 卷积为

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

性质

Dirichlet 卷积满足交换律和结合律。

其中 \varepsilon 为 Dirichlet 卷积的单位元(任何函数卷 \varepsilon 都为其本身)

例子

\begin{aligned} \varepsilon=\mu \ast 1&\iff\varepsilon(n)=\sum_{d\mid n}\mu(d)\\ d=1 \ast 1&\iff d(n)=\sum_{d\mid n}1\\ \sigma=d \ast 1&\iff\sigma(n)=\sum_{d\mid n}d\\ \varphi=\mu \ast \text{ID}&\iff\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d}) \end{aligned}

莫比乌斯函数

定义

\mu 为莫比乌斯函数,定义为

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

详细解释一下:

n=\prod_{i=1}^kp_i^{c_i} ,其中 p_i 为质因子, c_i\ge 1 。上述定义表示:

  1. n=1 时, \mu(n)=1
  2. 对于 n\not= 1 时:
    1. 当存在 i\in [1,k] ,使得 c_i > 1 时, \mu(n)=0 ,也就是说只要某个质因子出现的次数超过一次, \mu(n) 就等于 0
    2. 当任意 i\in[1,k] ,都有 c_i=1 时, \mu(n)=(-1)^k ,也就是说每个质因子都仅仅只出现过一次时,即 n=\prod_{i=1}^kp_i \{p_i\}_{i=1}^k 中个元素唯一时, \mu(n) 等于 -1 k 次幂,此处 k 指的便是仅仅只出现过一次的质因子的总个数。

性质

莫比乌斯函数不但是积性函数,还有如下性质:

\sum_{d\mid n}\mu(d)= \begin{cases} 1&n=1\\ 0&n\neq 1\\ \end{cases}

\sum_{d\mid n}\mu(d)=\varepsilon(n) ,即 \mu * 1 =\varepsilon

证明

\displaystyle n=\prod_{i=1}^k{p_i}^{c_i},n'=\prod_{i=1}^k p_i

那么 \displaystyle\sum_{d\mid n}\mu(d)=\sum_{d\mid n'}\mu(d)=\sum_{i=0}^k C_k^i\cdot(-1)^i=(1+(-1))^k

根据二项式定理,易知该式子的值在 k=0 n=1 时值为 1 否则为 0 ,这也同时证明了 \displaystyle\sum_{d\mid n}\mu(d)=[n=1]=\varepsilon(n) 以及 \mu\ast 1=\varepsilon

补充结论

反演结论: \displaystyle [\gcd(i,j)=1] \iff\sum_{d\mid\gcd(i,j)}\mu(d)

直接推导 :如果看懂了上一个结论,这个结论稍加思考便可以推出:如果 \gcd(i,j)=1 的话,那么代表着我们按上个结论中枚举的那个 n 1 ,也就是式子的值是 1 ,反之,有一个与 [\gcd(i,j)=1] 相同的值: 0

利用 \varepsilon 函数 :根据上一结论, [\gcd(i,j)=1]\implies \varepsilon(\gcd(i,j)) ,将 \varepsilon 展开即可。

线性筛

由于 \mu 函数为积性函数,因此可以线性筛莫比乌斯函数(线性筛基本可以求所有的积性函数,尽管方法不尽相同)。

线性筛实现
void getMu() {
  mu[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!flg[i]) p[++tot] = i, mu[i] = -1;
    for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
      flg[i * p[j]] = 1;
      if (i % p[j] == 0) {
        mu[i * p[j]] = 0;
        break;
      }
      mu[i * p[j]] = -mu[i];
    }
  }
}

拓展

证明

\varphi \ast 1=\text{ID}\text{(ID 函数即 } f(x)=x\text{)}

n 分解质因数: \displaystyle n=\prod_{i=1}^k {p_i}^{c_i}

首先,因为 \varphi 是积性函数,故只要证明当 n'=p^c \displaystyle\varphi \ast 1=\sum_{d\mid n'}\varphi(\frac{n'}{d})=\text{ID} 成立即可。

因为 p 是质数,于是 d=p^0,p^1,p^2,\cdots,p^c

易知如下过程:

\begin{aligned} \varphi \ast 1&=\sum_{d\mid n}\varphi(\frac{n}{d})\\ &=\sum_{i=0}^c\varphi(p^i)\\ &=1+p^0\cdot(p-1)+p^1\cdot(p-1)+\cdots+p^{c-1}\cdot(p-1)\\ &=p^c\\ &=\text{ID}\\ \end{aligned}

该式子两侧同时卷 \mu 可得 \displaystyle\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d})


莫比乌斯反演

公式

f(n),g(n) 为两个数论函数。

如果有

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

那么有

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

证明

方法一:对原式做数论变换。

\sum_{d\mid n}\mu(d)f(\frac{n}{d})=\sum_{d\mid n}\mu(d)\sum_{k\mid \frac{n}{d}}g(k)=\sum_{k\mid n}g(k)\sum_{d\mid \frac{n}{k}}\mu(d)=g(n)

\displaystyle\sum_{d\mid n}g(d) 来替换 f(\dfrac{n}{d}) ,再变换求和顺序。最后一步变换的依据: \displaystyle\sum_{d\mid n}\mu(d)=[n=1] ,因此在 \dfrac{n}{k}=1 时第二个和式的值才为 1 。此时 n=k ,故原式等价于 \displaystyle\sum_{k\mid n}[n=k]\cdot g(k)=g(n)

方法二:运用卷积。

原问题为:已知 f=g\ast1 ,证明 g=f\ast\mu

易知如下转化: f\ast\mu=g*1*\mu\implies f\ast\mu=g (其中 1\ast\mu=\varepsilon )。


问题形式

「HAOI 2011」Problem b

求值(多组数据)

\sum_{i=x}^{n}\sum_{j=y}^{m}[\gcd(i,j)=k]\qquad (1\leqslant T,x,y,n,m,k\leqslant 5\times 10^4)

根据容斥原理,原式可以分成 4 块来处理,每一块的式子都为

\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k]

考虑化简该式子

\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1]

因为 \gcd(i,j)=1 时对答案才用贡献,于是我们可以将其替换为 \varepsilon(\gcd(i,j)) \varepsilon(n) 当且仅当 n=1 时值为 1 否则为 0 ),故原式化为

\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\varepsilon(\gcd(i,j))

\varepsilon 函数展开得到

\displaystyle\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d\mid \gcd(i,j)}\mu(d)

变换求和顺序,先枚举 d\mid \gcd(i,j) 可得

\displaystyle\sum_{d=1}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}[d\mid i]\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[d\mid j]

易知 1\sim\lfloor\dfrac{n}{k}\rfloor d 的倍数有 \lfloor\dfrac{n}{kd}\rfloor 个,故原式化为

\displaystyle\sum_{d=1}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor

很显然,式子可以数论分块求解。

时间复杂度 \Theta(N+T\sqrt{n})

代码实现
#include <algorithm>
#include <cstdio>
const int N = 50000;
int mu[N + 5], p[N + 5];
bool flg[N + 5];
void init() {
  int tot = 0;
  mu[1] = 1;
  for (int i = 2; i <= N; ++i) {
    if (!flg[i]) {
      p[++tot] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= tot && i * p[j] <= N; ++j) {
      flg[i * p[j]] = 1;
      if (i % p[j] == 0) {
        mu[i * p[j]] = 0;
        break;
      }
      mu[i * p[j]] = -mu[i];
    }
  }
  for (int i = 1; i <= N; ++i) mu[i] += mu[i - 1];
}
int solve(int n, int m) {
  int res = 0;
  for (int i = 1, j; i <= std::min(n, m); i = j + 1) {
    j = std::min(n / (n / i), m / (m / i));
    res += (mu[j] - mu[i - 1]) * (n / i) * (m / i);
  }
  return res;
}
int main() {
  int T, a, b, c, d, k;
  init();
  for (scanf("%d", &T); T; --T) {
    scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
    printf("%d\n", solve(b / k, d / k) - solve(b / k, (c - 1) / k) -
                       solve((a - 1) / k, d / k) +
                       solve((a - 1) / k, (c - 1) / k));
  }
  return 0;
}

「SPOJ 5971」LCMSUM

求值(多组数据)

\sum_{i=1}^n \text{lcm}(i,n)\quad \text{s.t.}\ 1\leqslant T\leqslant 3\times 10^5,1\leqslant n\leqslant 10^6

易得原式即

\sum_{i=1}^n \frac{i\cdot n}{\gcd(i,n)}

将原式复制一份并且颠倒顺序,然后将 n 一项单独提出,可得

\frac{1}{2}\cdot \left(\sum_{i=1}^{n-1}\frac{i\cdot n}{\gcd(i,n)}+\sum_{i=n-1}^{1}\frac{i\cdot n}{\gcd(i,n)}\right)+n

根据 \gcd(i,n)=\gcd(n-i,n) ,可将原式化为

\frac{1}{2}\cdot \left(\sum_{i=1}^{n-1}\frac{i\cdot n}{\gcd(i,n)}+\sum_{i=n-1}^{1}\frac{i\cdot n}{\gcd(n-i,n)}\right)+n

两个求和式中分母相同的项可以合并。

\frac{1}{2}\cdot \sum_{i=1}^{n-1}\frac{n^2}{\gcd(i,n)}+n

\frac{1}{2}\cdot \sum_{i=1}^{n}\frac{n^2}{\gcd(i,n)}+\frac{n}{2}

可以将相同的 \gcd(i,n) 合并在一起计算,故只需要统计 \gcd(i,n)=d 的个数。当 \gcd(i,n)=d 时, \displaystyle\gcd(\frac{i}{d},\frac{n}{d})=1 ,所以 \gcd(i,n)=d 的个数有 \displaystyle\varphi(\frac{n}{d}) 个。

故答案为

\frac{1}{2}\cdot\sum_{d\mid n}\frac{n^2\cdot\varphi(\frac{n}{d})}{d}+\frac{n}{2}

变换求和顺序,设 \displaystyle d'=\frac{n}{d} ,合并公因式,式子化为

\frac{1}{2}n\cdot\left(\sum_{d'\mid n}d'\cdot\varphi(d')+1\right)

\displaystyle \text{g}(n)=\sum_{d\mid n} d\cdot\varphi(d) ,已知 \text{g} 为积性函数,于是可以 \Theta(n) 筛出。每次询问 \Theta(1) 计算即可。

这个函数筛的时候比较特殊,当 p_j\mid i 的时候,需要根据 p_j\mid\dfrac{i}{p_j} 进行分类讨论。具体可以见代码。

时间复杂度 \Theta(n+T)

代码实现
#include <cstdio>
const int N = 1000000;
int tot, p[N + 5];
long long g[N + 5];
bool flg[N + 5];

void solve() {
  g[1] = 1;
  for (int i = 2; i <= N; ++i) {
    if (!flg[i]) p[++tot] = i, g[i] = i * (i - 1) + 1;
    for (int j = 1; j <= tot && i * p[j] <= N; ++j) {
      flg[i * p[j]] = 1;
      if (i % p[j] == 0) {
        if ((i / p[j]) % p[j] == 0) {
          g[i * p[j]] = g[i] + (g[i] - g[i / p[j]]) * p[j] * p[j];
        } else {
          g[i * p[j]] = g[i] + g[i / p[j]] * (p[j] - 1) * p[j] * p[j] * p[j];
        }
        break;
      }
      g[i * p[j]] = g[i] * g[p[j]];
    }
  }
}
int main() {
  int T, n;
  solve();
  for (scanf("%d", &T); T; --T) {
    scanf("%d", &n);
    printf("%lld\n", (g[n] + 1) * n / 2);
  }
  return 0;
}

「BZOJ 2154」Crash 的数字表格

求值(对 20101009 取模)

\sum_{i=1}^n\sum_{j=1}^m\text{lcm}(i,j)\qquad (n,m\leqslant 10^7)

易知原式等价于

\sum_{i=1}^n\sum_{j=1}^m\frac{i\cdot j}{\gcd(i,j)}

枚举最大公因数 d ,显然两个数除以 d 得到的数互质

\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid i,d\mid j,\gcd(\frac{i}{d},\frac{j}{d})=1}\frac{i\cdot j}{d}

非常经典的 \gcd 式子的化法

\sum_{d=1}^n d\cdot\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]\ i\cdot j

后半段式子中,出现了互质数对之积的和,为了让式子更简洁就把它拿出来单独计算。于是我们记

\text{sum}(n,m)=\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=1]\ i\cdot j

接下来对 \text{sum}(n,m) 进行化简。首先枚举约数,并将 [\gcd(i,j)=1] 表示为 \varepsilon(\gcd(i,j))

\sum_{d=1}^n\sum_{d\mid i}^n\sum_{d\mid j}^m\mu(d)\cdot i\cdot j

i=i'\cdot d j=j'\cdot d ,显然式子可以变为

\sum_{d=1}^n\mu(d)\cdot d^2\cdot\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i\cdot j

观察上式,前半段可以预处理前缀和;后半段又是一个范围内数对之和,记

g(n,m)=\sum_{i=1}^n\sum_{j=1}^m i\cdot j=\frac{n\cdot(n+1)}{2}\times\frac{m\cdot(m+1)}{2}

可以 \Theta(1) 求解

至此

\text{sum}(n,m)=\sum_{d=1}^n\mu(d)\cdot d^2\cdot g(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)

我们可以 \lfloor\frac{n}{\lfloor\frac{n}{d}\rfloor}\rfloor 数论分块求解 \text{sum}(n,m) 函数。

在求出 \text{sum}(n,m) 后,回到定义 \text{sum} 的地方,可得原式为

\sum_{d=1}^n d\cdot\text{sum}(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)

可见这又是一个可以数论分块求解的式子!

本题除了推式子比较复杂、代码细节较多之外,是一道很好的莫比乌斯反演练习题!(上述过程中,默认 n\leqslant m

时间复杂度: \Theta(n+m) (瓶颈为线性筛)

代码实现
#include <algorithm>
#include <cstdio>
using std::min;

const int N = 1e7;
const int mod = 20101009;
int n, m, mu[N + 5], p[N / 10 + 5], sum[N + 5];
bool flg[N + 5];

void init() {
  mu[1] = 1;
  int tot = 0, k = min(n, m);
  for (int i = 2; i <= k; ++i) {
    if (!flg[i]) p[++tot] = i, mu[i] = -1;
    for (int j = 1; j <= tot && i * p[j] <= k; ++j) {
      flg[i * p[j]] = 1;
      if (i % p[j] == 0) {
        mu[i * p[j]] = 0;
        break;
      }
      mu[i * p[j]] = -mu[i];
    }
  }
  for (int i = 1; i <= k; ++i)
    sum[i] = (sum[i - 1] + 1LL * i * i % mod * (mu[i] + mod)) % mod;
}
int Sum(int x, int y) {
  return (1LL * x * (x + 1) / 2 % mod) * (1LL * y * (y + 1) / 2 % mod) % mod;
}
int func(int x, int y) {
  int res = 0;
  for (int i = 1, j; i <= min(x, y); i = j + 1) {
    j = min(x / (x / i), y / (y / i));
    res = (res + 1LL * (sum[j] - sum[i - 1] + mod) * Sum(x / i, y / i) % mod) %
          mod;
  }
  return res;
}
int solve(int x, int y) {
  int res = 0;
  for (int i = 1, j; i <= min(x, y); i = j + 1) {
    j = min(x / (x / i), y / (y / i));
    res = (res +
           1LL * (j - i + 1) * (i + j) / 2 % mod * func(x / i, y / i) % mod) %
          mod;
  }
  return res;
}
int main() {
  scanf("%d%d", &n, &m);
  init();
  printf("%d\n", solve(n, m));
}

「SDOI2015」约数个数和

多组数据,求

\sum_{i=1}^n\sum_{j=1}^md(i\cdot j)\\ \left(d(n)=\sum_{i \mid n}1\right) n,m,T\leq5\times10^4

其中 d(n) 表示 n 的约数个数

要推这道题首先要了解 d 函数的一个特殊性质

d(i\cdot j)=\sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y)=1]

再化一下这个式子

\begin{split} d(i\cdot j)=&\sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y)=1]\\ =&\sum_{x \mid i}\sum_{y \mid j}\sum_{p \mid \gcd(x,y)}\mu(p)\\ =&\sum_{p=1}^{min(i,j)}\sum_{x \mid i}\sum_{y \mid j}[p \mid \gcd(x,y)]\cdot\mu(p)\\ =&\sum_{p \mid i,p \mid j}\mu(p)\sum_{x \mid i}\sum_{y \mid j}[p \mid \gcd(x,y)]\\ =&\sum_{p \mid i,p \mid j}\mu(p)\sum_{x \mid \frac{i}{p}}\sum_{y \mid \frac{j}{p}}1\\ =&\sum_{p \mid i,p \mid j}\mu(p)d\left(\frac{i}{p}\right)d\left(\frac{j}{p}\right)\\ \end{split}