莫比乌斯反演笔记
写下这篇笔记为日后迷路的自己引路
开始恶补数学
数论函数
数论函数指定义域为正整数的函数。
积性函数
例子:
除数函数
除数函数
约数个数
除数函数都是积性函数
函数
性质
对于
单位函数
卷积
设
单位函数
计算卷积
如要计算
若
恒等函数
定义
则
注:本文用
莫比乌斯函数
前置知识:数论分块 | Jer's blog
定义
定义函数
可表示为
莫比乌斯反演定理
定理指出公式
例题
又到了喜闻乐见的例题环节
YY的GCD
求:
其中
代码略。
Crash的数字表格
求:
原式等同于
答案为 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
using namespace std;
long long n ,m;
long long mod=20101009;
inline long long g(long long n ,long long m){
return (n*(n+1)/2%mod)*(m*(m+1)/2%mod)%mod;
}
long long a[10000001];
long long mu[10000001] ,p[1000001] ,cur;
bool vis[10000001];
void init()
{
mu[1]=1;
for(int i=2;i<=min(n ,m);i++){
if(!vis[i]){
p[++cur]=i;
mu[i]=-1;
}
for(int j=1;j<=cur&&p[j]*i<=min(n ,m);j++){
vis[p[j]*i]=1;
if(i%p[j]==0){
break;
}
mu[i*p[j]]=-mu[i];
}
}
for(int i=1;i<=min(n,m);i++)
a[i]=(a[i-1]+i*i%mod*(mu[i]+mod)%mod)%mod;
}
long long f(long long n ,long long m){
long long ans=0;
for(int i=1,j;i<=min(n,m);i=j+1){//优化,理性理解,背住即可,下同
j=min(n/(n/i),m/(m/i));
ans=(ans+(a[j]-a[i-1]+mod)*g(n/i,m/i)%mod)%mod;
}
return ans;
}
main()
{
cin >> n >> m;
init();
long long ans=0;
for(int i=1,j;i<=min(n,m);i=j+1){
j=min(n/(n/i),m/(m/i));
ans=(ans+(j-i+1)*(i+j)/2%mod*f(n/i,m/i)%mod)%mod;
}
cout << ans << endl;
}
[SDOI2015]约数个数和
求
解
有一个公式
1 |
|
平方因子
求小于
这一道题表现了莫比乌斯函数真正意义
由莫比乌斯函数定义明显可以得到
对于质数
但这样减去会导致多减去如
可用容斥原理解。
如果
是 个不同素数的乘积,它对答案的贡献为如果
有平方因子,它对答案无贡献。
可以发现容斥系数恰好是莫比乌斯函数。
答案为
总结
以Crash的数字表格为例,总结莫比乌斯反演套路。
套路
得
设