Luckyleaves's Blog

stay hungry,stay foolish greedy and lucky

莫比乌斯反演

前置知识

整数分块

整除分块是用于快速处理形似 i=1nni 的式子的方法
很显然,这个可以O(n)得到答案。但是,在某些题目中,毒瘤出题人将数据加强到了 1010 以上,这个时候我们就无法通过O(n)的解法来得到答案了。我们需要一个O(n)的更为优秀的解法
首先观察这个式子,找几个特殊值代入
n=5时,sum=5+2+1+1+1
可以发现的是:(这里给的例子并不明显,其实应该找一个大的n来代入才直观,读者可以自行尝试)
对于单一的ni,某些地方的值是相同的,并且呈块状分布
通过进一步的探求规律与推理以及打表与瞎猜,我们可以惊喜的发现一个规律,这些块状分布的值是有规律的
对于一个块,假设它的起始位置的下标为l,那么可以得到的是,它的结束位置的下标为nni
如果实在看的有点懵逼,可以继续采用代入特殊值的方法,验证一下上方的规律,用程序表现出来即为

1
2
3
4
5
for(int l = 1, r;l <= n;l = r + 1)
{
r = n / (n / l);
ans += (r - l + 1) * mu[l];//mu只是举个例子,可以带入任意符合的函数
}

重要函数:
μ(x)={0(di2)1(di=1)

I=1

简介

  • 莫比乌斯反演主要用来简化运算,通常有性质:

F(n)=d|nf(d)f(n)=d|nμ(d)F(nd)

简要证明:

1.直接证

d|nμ(d)F(nd)=d|nμ(d)i|ndf(i)=i|nf(i)d|niμ(d)=i|nf(i)[ni==1]=f(n)

2.运用狄利克雷卷积

F=fIFμ=fIμ(Iμ)=εFμ=fε=ff=μF

如果看不懂的话, 我将1的详细步骤写一下:

我们将原式化简可得
f(x)=d|nμ(d)i|ndf(i)

我们令
S(n)=d|nμ(d)
即可化简的
S(n)=[n==1]
我们再令
d=nd
带回原式可得
f(n)=d|nμ(d)i|ndf(i)
我们不妨设x = n / d, 则x * d = n, 那么当x确定时,d同样也确定,反之亦然同理, 则f(x)和μ(d)所枚举到的数完全一样,即我们可以交换f(x)和μ(d),那么原式即可变形为
f(n)=i|nf(i)d|niμ(d)
此时我们再联想到S(x), 再令x = n / i, 就可以得到
f(i)=i|nf(i)S(ni)

此时再将F(n)代回

(1)n|dμ(dn)F(d)=n|dμ(dn)d|if(i)(2)=n|if(i)d|inμ(d)(3)=f(n)

证毕

例题:luogu P2257 YY的GCD

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
using namespace std;
const int N = 1e7 + 10;
int prime[N], cnt, n, phi[N], g[N];
bool d[N];
LL s[N];
void init()
{
phi[1] = 1;
for (int i = 2;i < N;i ++)
{
if (!d[i]) prime[++ cnt] = i, phi[i] = - 1;
for (int j = 1;j <= cnt && i * prime[j] < N;j ++)
{
d[i * prime[j]] = 1;
if (i % prime[j] == 0)
{
phi[i * prime[j]] = 0;
break;
}
else phi[i * prime[j]] = - phi[i];
}
}
for(int j = 1;j <= cnt;j ++)
{
for(int i = 1;i * prime[j] < N;i ++)
{
g[i * prime[j]] += phi[i];
}
}
for (int i = 2;i < N;i ++) s[i] = s[i - 1] + g[i];
}
int T;
LL ans;
int m;
int main()
{
init();
scanf("%d", &T);
while(T --)
{
ans = 0;
scanf("%d %d", &n, &m);
if(n > m) swap(n, m);
for (int l = 1, r;l <= n;l = r + 1)
{
r = min(n, min(n / (n / l), m / (m / l)));
ans += (s[r] - s[l - 1]) * (LL)(n / l) * (m / l);
}
printf("%lld\n", ans);
}
return 0;
}