莫比乌斯反演简要笔记

Published on 2016-08-18

终于学了一波莫比乌斯反演,感觉一些技巧还是容易忘的,记一下方便回顾。

莫比乌斯函数

定义

莫比乌斯函数 μ(n)\mu(n) 的定义:
n=p1k1p2k2pmkmn = p_1 ^ {k_1} \cdot p_2 ^ {k_2} \cdot\cdots\cdot p_m ^ {k_m},其中 pp 为素数,则定义如下:

μ(n)={1n=1(1)mi=1mki=10otherwise(ki>1) \mu(n) = \begin{cases} 1 & n = 1 \\ (-1) ^ m & \prod\limits_{i = 1} ^ {m} k_i = 1 \\ 0 & \textrm{otherwise}(k_i \gt 1) \end{cases}

可知有平方因子的数的莫比乌斯函数值为 00

性质

性质一:莫比乌斯函数是积性函数。

μ(a)μ(b)=μ(ab),ab \mu(a)\mu(b) = \mu(a\cdot b), a\perp b

应用:根据这一性质,我们可以采取线性筛法,用 O(n)O(n) 的时间预处理出所有 [1,n][1, n] 内的莫比乌斯函数值。
质数的值为 1-1,如果一个数存在某个质因子的指数不为 11,那么它将会被筛为 00(值得注意的是,只有数存在最小质因子的指数大于 11 时,它才会被直接筛为 00,其余的情况是由 μ(d)=μ(i)\mu(d) = -\mu(i) 来完成的)。
每个数仅被其最小质因子筛去,故复杂度为 O(n)O(n)

void sieve() {
    fill(isPrime, isPrime + maxn, 1);
    mu[1] = 1, num = 0;
    for (int i = 2; i < maxn; ++i) {
        if (isPrime[i]) primes[num++] = i, mu[i] = -1;
        static int d;
        for (int j = 0; j < num && (d = i * primes[j]) < maxn; ++j) {
            isPrime[d] = false;
            if (i % primes[j] == 0) {
                mu[d] = 0;
                break;
            } else mu[d] = -mu[i];
        }
    }
}

性质二:

dnμ(d)=[n=1] \sum_{d\mid n}\mu(d) = [n = 1]

证明:n=1n = 1 时有 μ(1)=1\mu(1) = 1,显然成立。否则设 n=p1k1p2k2pmkmn = p_1 ^ {k_1} \cdot p_2 ^ {k_2} \cdot\cdots\cdot p_m ^ {k_m}d=p1x1p2x2pmxmd = p_1 ^ {x_1} \cdot p_2 ^ {x_2} \cdot\cdots\cdot p_m ^ {x_m} 根据 μ\mu 的定义,只需考虑 xi=0x_i = 0xi=1x_i = 1 的情况。我们设 dd 中存在 rrxix_i 为 1,那么有:

dnμ(d)=r=0m(mr)(1)r(n1)\sum_{d\mid n}\mu(d) = \sum_{r = 0}^m\binom m r(-1)^r(n \neq 1)

根据二项式定理

(x+y)n=k=0n(nk)xnkyk (x+y)^{n}=\sum _{k=0}^{n}\binom n kx^{n-k}y^{k}

我们令 x=1,y=1x = 1, y = -1,即得证:

r=0m(mr)(1)r=(11)m=0(n1) \sum_{r = 0}^m\binom m r(-1)^r = (1 - 1)^m = 0(n \neq 1)

此公式运用的很多,在求 gcd=1\gcd = 1 或是用杜教筛求前缀和的时候都用的到。

莫比乌斯反演

公式

如果 f(n),g(n)f(n), g(n)数论函数,且满足:

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

则有莫比乌斯反演:

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

证明:

dnμ(d)f(nd)=dnμ(d)indg(i)=ing(i)kniμ(k)=g(n) \begin{aligned} &\sum_{d\mid n}\mu(d)f(\frac n d)\\=&\sum_{d\mid n}\mu(d)\sum_{i\mid \frac n d}g(i)\\=&\sum_{i\mid n}g(i)\sum_{k\mid \frac n i}\mu(k)\\=&g(n) \end{aligned}

根据莫比乌斯函数的性质 2,可知当且仅当 i=ni = n 时和式的值为 g(n)g(n),否则为 00

变形

f(i)=d=1nig(di)g(i)=d=1nif(di)μ(d) f(i) = \sum_{d = 1}^{\left\lfloor\frac n i\right\rfloor}g(d\cdot i)\Rightarrow g(i) = \sum_{d = 1}^{\left\lfloor\frac n i\right\rfloor}f(d\cdot i)\mu(d)

证明就略过了,与上面的证明大同小异,可以做为练习加深理解。

应用

所有和式默认 nmn\le m,不满足则交换。

求 gcd = k 的个数

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

f(k)f(k)gcd(i,j)=k\gcd(i, j) = k 的个数,g(k)g(k) 为满足 kgcd(i,j)k\mid\gcd(i, j) 的对数,则有以下关系:

g(k)=x=1nkf(kx)g(k) = \sum_{x = 1}^{\left\lfloor\frac n k\right\rfloor}f(k\cdot x)

我们只需快速求出 g(k)g(k),可知,如果 i,ji, j 能被 kk 整除,那么它们可以写成 i=kx1,j=kx2i = k\cdot x_1, j = k\cdot x_2 的形式,我们只需求有多少对 x1,x2x_1, x_2 即可,可得:

g(k)=nkmkg(k) = \left\lfloor\frac n k\right\rfloor\left\lfloor\frac m k\right\rfloor

根据莫比乌斯反演的变形,可求得 f(k)f(k)

f(k)=x=1nkμ(x)g(kx)=x=1nkμ(x)nkxmkx\begin{aligned}f(k) &= \sum_{x = 1}^{\left\lfloor\frac n k\right\rfloor}\mu(x)g(k\cdot x)\\&=\sum_{x = 1}^{\left\lfloor\frac n k\right\rfloor}\mu(x)\left\lfloor\frac n {kx}\right\rfloor\left\lfloor\frac m {kx}\right\rfloor\end{aligned}

显然 f(k)f(k) 就是答案,暴力求是 O(n)O(n) 的。如何快速求?这里很重要的思想就是分块,nd\left\lfloor\frac n d\right\rfloor 有至多 O(n)O(\sqrt n) 个取值。

证明:1d<n1\le d< \sqrt n 时,由于 dd 只有 n\sqrt n 个,所以 nd\left\lfloor\frac n d\right\rfloor 也只有至多 n\sqrt n 个取值。
ndn\sqrt n\le d\le n 时,由于 nd\left\lfloor\frac n d\right\rfloor 小于 n\sqrt n,所以 nd\left\lfloor\frac n d\right\rfloor 也只有至多 n\sqrt n 个取值。
nd\left\lfloor\frac n d\right\rfloor 有至多 O(n)O(\sqrt n) 个取值,证明完毕。

同理 md\left\lfloor\frac m d\right\rfloor 也只有至多 m\sqrt m 个取值,又因为取值是连续的,所以 nkx\left\lfloor\frac n {kx}\right\rfloormkx\left\lfloor\frac m {kx}\right\rfloor 同时不变的段数有 O(n+m)O(\sqrt n + \sqrt m) 个。

例:n=32,m=40,k=2n = 32, m = 40, k = 2,红色为相等的段。

对于相等的段,我们求取 μ\mu 的前缀和,即可批量计算这一个段的答案。

ll F(int n, int m, int d) {
    if (n > m) swap(n, m);
    ll ans = 0;
    n /= d, m /= d;
    for (int i = 1, last = 1; i <= n; i = last + 1) {
        last = min(n / (n / i), m / (m / i));
        ans += (ll)(sum[last] - sum[i - 1]) * (n / i) * (m / i);
    } 
    return ans;
}

对于位置 ii,找到下一个相等的位置的代码为 min(n / (n / i), m / (m / i))。对于 nn 来说,我们要找到最大的 jj,满足:

njni\lfloor\frac n j\rfloor \ge \lfloor\frac n i\rfloor

可以拆掉左边的底:

njni\frac n j\ge \lfloor\frac n i\rfloor

继续化简:

jnnij\le \left\lfloor\frac n {\lfloor\frac n i\rfloor}\right\rfloor

所以 j=nnij = \left\lfloor\frac n {\lfloor\frac n i\rfloor}\right\rfloor,对 mm 同理,取两个 jj 最小值即为都不变的段 [i,j][i, j]

总之,复杂度为 O(n+m)O(\sqrt n + \sqrt m)
这个 f(k)f(k) 以及分块非常重要,几乎题题都会用到。

gcd(i, j) 的幂

i=1nj=1mgcd(i,j)kmod(109+7)\sum_{i = 1}^n\sum_{j = 1}^m\gcd(i, j)^k \bmod ({10}^9 + 7)

按照我们刚刚的技巧,枚举最大公约数 dd 然后转换为可分块的形式:

i=1nj=1mgcd(i,j)k=d=1ndki=1nj=1m[gcd(i,j)=d]=d=1ndkx=1ndμ(x)ndxmdx\begin{aligned}\sum_{i = 1}^n\sum_{j = 1}^m\gcd(i, j)^k& = \sum_{d = 1}^nd^k\sum_{i = 1}^n\sum_{j = 1}^m[\gcd(i, j) = d]\\& = \sum_{d = 1}^nd^k\sum_{x=1}^{\left\lfloor\frac n d\right\rfloor}\mu(x)\left\lfloor\frac n {dx}\right\rfloor\left\lfloor\frac m {dx}\right\rfloor\end{aligned}

到这里可以分套分块 O((n)2)=O(n)O((\sqrt n)^2) = O(n),如果多组询问怎么办呢?另一重要技巧就是枚举 dxdx,你可能会疑惑,d,xd, x 都没定呢,怎么枚举 dxdx?实际上我们枚举的是乘积,让 dxdx 为定值,这个情况下再枚举 dd

原式可化为:

T=1nndxmdxdndkμ(Td)\sum_{T=1}^n\left\lfloor\frac n {dx}\right\rfloor\left\lfloor\frac m {dx}\right\rfloor\sum_{d \mid n}d^k\mu(\frac T d)

这样的求出答案是正确的吗?我们知道之前一步的式子是:d=1ndkx=1ndμ(x)ndxmdx\sum_{d = 1}^nd^k\sum_{x=1}^{\left\lfloor\frac n d\right\rfloor}\mu(x)\left\lfloor\frac n {dx}\right\rfloor\left\lfloor\frac m {dx}\right\rfloor

显然只要 dd 以及 xx 定了,式子的一项也就定了,于是原式也可以写成;

(d,x)dkμ(x)ndxmdx\sum_{(d, x)} d^k\mu(x)\left\lfloor\frac n {dx}\right\rfloor\left\lfloor\frac m {dx}\right\rfloor

只要我们能枚举出所有的二元组 (d,x)(d, x),并把对应项乘起来,就是正确的。

如果设 f(n)=dndkμ(Td)f(n) = \sum_{d \mid n}d^k\mu(\frac T d),则我们只需要求 ff 的一个前缀和就可以 O(n)O(\sqrt n) 回答询问了。
发现 dkd^k 是积性函数,根据莫比乌斯反演的性质,ff 也是一个积性函数,我们可以线筛 O(n)O(n) 求出答案。

怎么线筛?如果对于积性函数 ff 来说,f(pk),p is a primef(p^k), \textrm{p is a prime}O(1)O(1) 求出的话,那么就可以 O(n)O(n) 预处理了,详见 线性筛法与积性函数
所以我们要想办法快速处理 f(pk)f(p^k),通常要分解质因数来考虑。

这里化一下 ff

f(n)=dndkμ(Td)=pif(pixi)=pi(pixiμ(1)+pik(xi1)μ(pi))=pipik(xi1)(pik1)\begin{aligned}f(n)&= \sum_{d \mid n}d^k\mu(\frac T d)\\&= \prod_{p_i} f(p_i^{x_i})\\&= \prod_{p_i} (p_i^{x_i}\cdot\mu(1) + p_i^{k(x_i-1)}\cdot \mu(p_i))\\&= \prod_{p_i} p_i^{k(x_i-1)}(p_i^k-1)\end{aligned}

总复杂度:O(n+Tn)O(n + T\sqrt n)

其他技巧

题目太多了,我懒得写了。好像不少题目都是与“求 gcd(i,j)\gcd(i, j) 的幂”差不多的方法,最后都变成了线筛预处理积性函数了,那就不写了,记一下化简式子中可能用到的小技巧吧。

如果 d(n)d(n)nn 的约数个数,则:

d(nm)=injm[gcd(i,j)=1]d(nm) = \sum_{i\mid n}\sum_{j\mid m}[\gcd(i, j) = 1]

证明:nm=p1x1p2x2p3x3pkxknm = p_1^{x_1}\cdot p_2^{x_2}\cdot p_3^{x_3}\cdots p_k^{x_k},且 n=p1y1p2y2p3y3pkykn = p_1^{y_1}\cdot p_2^{y_2}\cdot p_3^{y_3}\cdots p_k^{y_k},则 m=p1x1y1p2x2y2p3x3y3pkxkykm = p_1^{x_1 - y_1}\cdot p_2^{x_2 - y_2}\cdot p_3^{x_3 - y_3}\cdots p_k^{x_k - y_k}
i=p1a1p2a2p3a3pkaki = p_1^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3}\cdots p_k^{a_k}j=p1b1p2b2p3b3pkbkj = p_1^{b_1}\cdot p_2^{b_2}\cdot p_3^{b_3}\cdots p_k^{b_k},要使 gcd(i,j)=1\gcd(i, j) = 1,必然有 a1a_1b1b_1 为 0,如果 a1a_1 为 0,那么 b1b_1xiy1+1x_i - y_1 + 1 种取值;如果 b1b_1 为 0,那么 a1a_1y1+1y_1 + 1 种取值,一共有 x1+1x_1 + 1 种取值,对于 xix_i 也如此。
所以满足条件的 i,ji, j 对数为 (xi+1)\prod(x_i + 1),与约数定理给出的形式一样,得证。

总结

还没写完怎么就总结了
莫比乌斯反演一般来说套路比较固定,看到两个求和符号,基本上就逃不开莫比乌斯了。
求和的东西可能不同,但是一般都与 gcd\gcd 有关,枚举 gcd\gcd,再使用 gcd=k\gcd = k 的个数 + 分块一般能 O(n)O(n),将后面的部分提前 + 积性函数预处理 + 分块一般能单组 O(n)O(\sqrt n)
积性函数有时不好数学证明,那么可以打表来验证,重点关注质数,质数的幂的值。
还有如果 n,mn, m 比较大的,可能需要使用杜教筛处理一下前缀和,需要一些数学功底来推导。
杜教筛我可能会新开一个笔记(填坑)。