mydcwfy's Blog

莫比乌斯反演

Posted on
Symbols count in article: 8.2k Reading time ≈ 18 mins.

容斥原理的升级版。

1. 莫比乌斯函数的定义与主要思想

$\mu(x)$ 来表示莫比乌斯函数。

其实就是容斥原理的升级版。

定义为：（假设 $x=p1^{a1}p2^{a2}…pk^{ak}$）

  1. $\exists i, ai\geq2,\mu(x)=0$
  2. $\forall i,ai=1,\mu(x)=(-1)^k$

顺便讲一下积性函数：

如果 $\gcd(i,j)=1,f(ij)=f(i)f(j)$，那么 $f$ 就是积性函数。

$\mu(x)$ 就是一个积性函数。

原因很简单：

  1. 如果有 $\mu(i)=0$ 或 $\mu(j)=0$，那么 $i j$ 一定有一个质因数的次数 $\geq2$，所以 $\mu(ij)=0$
  2. 如果没有，设 $i$ 的质因数个数（即上面的 $k$）为 $x$，$j$ 为 $y$，又因为 $\gcd(i,j)=1$，所以没有相同的质因数，所以 $i j$ 的质因数个数为 $x+y$，且没有次数 $>1$ 的。所以 $\mu(i j)=(-1)^{x+y}$。

那么，我们就可以在线性筛的时候求出 $\mu(x)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
mu[1]=1;
   for (int i=2;i<N;++i)
   {
       if (!st[i]) mu[i]=-1,prime[cnt++]=i;
       for (int j=0;j<cnt&&i*prime[j]<N;++j)
       {
           st[i*prime[j]]=1;
           if (!(i%prime[j]))
           {
               mu[i*prime[j]]=0;//break1
               break;
           }
           mu[i*prime[j]]=-mu[i];//break2
       }
   }

这就是一个简单的线性筛模板了。

break1：这时，$i prime[j]$ 的 $prime[j]$ 的次数一定大于 1，所以 $\mu(iprime[j])$ 为 0。

break2：这是，可以使用积性函数的性质 $\mu(i prime[j])=\mu(i) \mu(prime[j])$。

2. 函数的一些性质

一）

定义 $smu(n)=\sum_{d|n}\mu(d)$，那么可以得到：

  1. $n=1\Rightarrow smu(n)=1$
  2. $n\not=1,smu(n)=0$

简要的证明一下（前置知识：二项式定理）：

$n=1$ 的情况略过。

假设 $n>1$，那么 $k\geq1$（前面的 $k$，即质因数个数）

首先，如果 $\forall i,0\leq bi\leq ai$，那么 $x=p1^{b1}p2^{b2}…pk^{bk}$ 一定是 $n$ 的因数。

如果 $\exists bi>1$，那么 $\mu(x)=0$。

所以，我们只需要考虑 $0\leq bi\leq1$ 的情况。

假设有 $t$ 个 1，则 $\mu(x)=(-1)^t$。（不懂的回去看一下前面的定义）

对于每一个 $t$，其实都有 $C_k^t$ 种情况（就是 $k$ 个中选取 $t$ 个，就是组合数了）

那么，$smu(n)=C_k^0(-1)^0+C_k^1(-1)^1+…+C_k^{k-1}(-1)^{k-1}+C_k^k(-1)^k$。

又由二项式定义得到：$(a+b)^k=C_k^0a^0b^k+C_k^1a^1b^{k-1}+…+C_k^ka^kb_0$。

用 $-1$ 代替 $a$，$1$ 代替 $b$，我们发现， 右边就是 $smu(n)$，左边就是 $(-1+1)^k=0$！

得证。

3. 莫比乌斯反演

直接扔式子。

这个是比较常见的式子。

简要的证明一下：

上面的式子就是我们根据所给条件从右边开始的。

现在，我们要做一件事情：将 $d$ 和 $x$ 交换一下！

先给出结论：

为什么是对的呢？

这里，我们假设一下：首先有一个 $d$，然后我们枚举了 $\dfrac{n}{d}$ 的因数 $x$，然后我们将 $\mu(d)f(x)$ 加入了答案。

$x|\dfrac{n}{d}\Leftrightarrow xd|n$，那么，$xd|n\Leftrightarrow d|\dfrac{n}{x}$。

所以，我们枚举每一个 $x$，其实和枚举每一个 $d$ 其实是一样的，因为每个枚举到的 $(x,d)$ 在先枚举 $d$ 的时候都会枚举到！

那么，原式变为了：

观察右边的 $\displaystyle \sum_{d|\frac{n}{x}}\mu(d)$，和上面我们得到的式子 $smu(n)$ 其实是一样的！

所以，只有在 $\dfrac{n}{x}=1$，即 $x=n$ 时后面才为 1，其余为 0。

那么，原式得证。

你以为就结束了吗？

还有一个式子：

和上面的式子略微不同，但本质一样。

还是一波操作（中间步骤的推导留给读者 逃）：

设 $t=\dfrac{d}{n}$，$y=\dfrac{x}{d}$，则：

那么，我们在枚举 $t$ 再枚举 $y$ 的时候，统计答案为 $\mu(t) f(t y n)$，我们也可以先枚举 $t y$，在枚举 $t$，其实相当于枚举了 $t,y$。

所以，一波操作（设 $z=t * y$）：

所以又看到后面的式子，实在是熟悉不过了。

于是 $z=1$ 时右边为 $1$。

所以就是 $f(n)$ 了。

3. 例题

T1：[HAOI 2011]Problem b

题目传送门 Luogu

题目传送门 AcWing

首先，看到 $x\in[a,b],y\in[c,d]$，可以想到二维前缀和（还是差分，记不清楚了 qwq

所以，假设 $F(a,b)$ 表示 $x\in[1,a],y\in[1,b]$ 满足 $\gcd(x,y)=k$ 的个数，可以得到：

然后开始正题，求 $F(a,b)$。

又是一波操作：

首先，$[\gcd(x,y)=1]$ 表示 $\gcd(x,y)=1$ 取值为 $1$，否则为 $0$。

那么，设 $m=\dfrac{a}{k},n=\dfrac{b}{k}$，于是就是：

定义 $f(d)$ 为 $\sum_{x=1}^m\sum_{y=1}^n[\gcd(x,y)=d]$，$g(d)=\sum_{x=1}^m\sum_{y=1}^n[d|\gcd(x,y)]$。

所以 $F(a,b)=f(1)$，$g(x)=\lfloor\dfrac{m}{x}\rfloor\lfloor\dfrac{n}{x}\rfloor$。（直接取 $x$ 的倍数就是了

还有一个：

意义很简单：$\gcd(a1,a2)$ 可以等于 $x,2x,…$，就是这个式子的意思。

根据套路：

所以，$f(1)=\sum_{d=1}^n\mu(d)g(d)$

直接求的话，大概也是能过的。

还有一些优化，比如整除分块，就是 $g(d)$ 相同的可以一起计算。

如果当前的值为 $a$，那么当前值为 $\dfrac{n}{a}$，那么最大的 $x$ 满足 $\dfrac{n}{x}=\dfrac{n}{a}$ 为 $x=\dfrac{n}{\frac{n}{a}}$。（证明略复杂，跳过

加入 $m$ 的话，满足 $\dfrac{n}{a}\dfrac{m}{a}=\dfrac{n}{x}\dfrac{n}{x}$ 的最大 $x$ 为 $\min(\dfrac{n}{\frac{n}{a}},\dfrac {m}{\frac{m}{a}})$。

时间复杂度：$O(\sqrt{n})$。

放个代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef long long ll;

ll calc(int a,int b)
{
    a/=k,b/=k;
    ll res=0;
    int n=min(a,b);
    for (int l=1,r;l<=n;l=r+1)
    {
        r=min(n,min(a/(a/l),b/(b/l)));
        res+=(sum[r]-sum[l-1])*(ll)(a/l)*(b/l);
    }
    return res;
}

T2：[SDOI 2015]约数个数和

题目传送门 Luogu

题目传送门 AcWing

前方高能！

首先，得到结论：

简要证明：

假设对于每一个质因数 $p$，$i$ 的次数为 $a$，$j$ 的次数为 $b$。

对于左边，显然 $p$ 的存在可以使答案乘上 $a+b+1$（可以选择 $0\sim a+b$ 次方）。

对于右边，可以有以下的方法：

  1. 都选择 $0$ 次，贡献为 $1$。
  2. 如果 $i$ 选择 $0$ 次，那么 $j$ 可以选择 $1\sim b$，贡献为 $b$。
  3. 如果 $j$ 选择 $0$ 次，那么 $i$ 可以选择 $1\sim a$，贡献为 $a$。

综上，$p$ 的存在使得答案乘上了 $a+b+1$。

既然对于每一个 $p$，左右相乘的数是相等的。

得证。

接下来，一波操作：

根据上面的结论得到的。

直接提出 $x,y$，枚举 $i,j$ 贡献其实就是 $\lfloor\dfrac{N}{x}\rfloor\lfloor\dfrac{M}{y}\rfloor$。

令 $f(d)=\sum_{x=1}^N\sum_{y=1}^M[\gcd(x,y)=1]\lfloor\dfrac{N}{x}\rfloor\lfloor\dfrac{M}{y}\rfloor,F(d)=\sum_{x=1} ^N\sum_{y=1}^M[d|\gcd(x,y)]\lfloor\dfrac{N}{x}\rfloor\lfloor\dfrac{M}{y}\rfloor$。

还可以根据套路推 $F$ 得到：

接着令 $N1=\dfrac{N}{d},M1=\dfrac{M}{d}$，则：

$g(n)=\sum_{k=1}^{N}\lfloor\dfrac{N}{k}\rfloor$ 是可以预处理的。对于每一个 $g(n)$，直接整除分块，复杂度 $O(n\sqrt{n})$。

可以得到：$F(d)=g(\dfrac{N}{d})g(\dfrac{M}{d})$

莫比乌斯的反演套路大都如此：构造出 $f,F$，引入 $\mu$ 来简化运算，$f(1)$ 一般为所求，$\mu$ 一般要预处理。

接着：

可以 $O(n)$ 求，但还不够优秀。

带入 $g$，即得：

发现可以整除分块，单次复杂度为 $O(\sqrt{n})$，可以通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

typedef long long ll;
const int N = 5e4 + 10;
ll g[N];
int prime[N], cnt, mu[N], n, m, s[N];
bool st[N];

void init()
{
    int n = N - 1;
    mu[1] = 1;
    for (int i = 2; i <= n; ++ i)
    {
        if (!st[i]) prime[cnt ++] = i, mu[i] = -1;
        for (int j = 0; j < cnt && prime[j] * i <= n; ++ j)
        {
            st[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
            mu[i * prime[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= n; ++ i) s[i] = s[i - 1] + mu[i];
    for (int d = 1; d <= n; ++ d)
    {
        for (int l = 1, r; l <= d; l = r + 1)
        {
            r = d / (d / l);
            g[d] += (r - l + 1) * (d / l);
        }
    }
}

int main()
{
    init();
    int t;
    cin >> t;
    while (t --)
    {
        scanf("%d %d", &n, &m);
        if (n > m) swap(n, m);
        ll ans = 0;
        for (int l = 1, r; l <= n; l = r + 1)
        {
            r = min(n / (n / l), m / (m / l));
            ans += (s[r] - s[l - 1]) * g[n / l] * g[m / l];
        }
        cout << ans << endl;
    }
    return 0;
}

下面给出几道题目与得到的公式，就不展开了。

T3：P3312 [SDOI2014]数表

题目传送门 Luogu

$g(d)$ 表示 $d$ 的约数和。

T4：P3704 [SDOI2017]数字表格

题目传送门 Luogu

T5：P3768 简单的数学题

题目传送门 Luogu

后面使用杜教筛等。

化简为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <map>
using namespace std;

typedef long long ll;
const int N = 1e7 + 10;
ll Mod, sphi[N], n, inv2, inv6;
int prime[N], cnt, phi[N];
bool st[N];
map <ll, ll> Sphi;

void init()
{
	phi[1] = 1;
	for (int i = 2; i < N; ++ i)
	{
		if (!st[i]) prime[cnt ++] = i, phi[i] = i - 1;
		for (int j = 0; j < cnt && i * prime[j] < N; ++ j)
		{
			st[i * prime[j]] = 1, phi[i * prime[j]] = phi[i] * phi[prime[j]];
			if (i % prime[j] == 0)
			{
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
		}
	}
	for (int i = 1; i < N; ++ i) sphi[i] = (sphi[i - 1] + phi[i] * (ll)i % Mod * i % Mod) % Mod;
}

ll qpow(ll a, ll k)
{
	ll res = 1;
	while (k)
	{
		if (k & 1) res = res * a % Mod;
		a = a * a % Mod;
		k >>= 1;
	}
	return res;
}

inline ll sum1(ll n){return (n % Mod) * ((n + 1) % Mod) % Mod * inv2 % Mod;}
inline ll sum2(ll n){return (n % Mod) * ((n + 1) % Mod) % Mod * ((2 * n + 1) % Mod) % Mod * inv6 % Mod;}
inline ll sum3(ll n){return sum1(n) * sum1(n) % Mod;}

ll get_sphi(ll n)
{
	if (n < N) return sphi[n];
	if (Sphi.find(n) != Sphi.end()) return Sphi[n];
	ll ans = sum3(n);
	for (ll l = 2, r; l <= n; l = r + 1)
	{
		r = n / (n / l);
		ans = (-(sum2(r) - sum2(l - 1)) * get_sphi(n / l) % Mod + ans + Mod) % Mod;
	}
	return Sphi[n] = ans;
}

int main()
{
	cin >> Mod >> n;
	inv2 = qpow(2, Mod - 2), inv6 = qpow(6, Mod - 2);
	init();
	ll res = 0;
	for (ll l = 1, r; l <= n; l = r + 1)
	{
		r = n / (n / l);
		res = (res + sum1(n / l) * sum1(n / l) % Mod
        * ((get_sphi(r) - get_sphi(l - 1) + Mod) % Mod) % Mod) % Mod;
	}
	cout << res << endl;
	return 0;
}