写下这篇笔记为日后迷路的自己引路

开始恶补数学

数论函数

数论函数指定义域为正整数的函数。

积性函数

例子:

除数函数

除数函数用来表示的因子的k次方之和:

约数个数常记为,约数和常记为

除数函数都是积性函数

函数

表示不超过且与互质的正整数个数。 其中的标准分解。函数为积性函数。

性质

证明:

对于个。考虑所有得到式子。

单位函数

==

卷积

是数论函数,数论函数满足 卷积,记作

单位函数卷积的单位元,则 卷积满足交换律和结合律。

计算卷积

如要计算项,枚举~的倍数,时间复杂度为

为积性函数可进一步降为,参见欧拉筛。

恒等函数

定义

注:本文用来表示取值恒为的常函数

莫比乌斯函数

前置知识:数论分块 | Jer's blog

定义

函数定义为: ### 性质 卷积表示为 ### 莫比乌斯变换

定义函数满足公式 其中为数论函数。称的莫比乌斯变换,的莫比乌斯逆变换。

可表示为

莫比乌斯反演定理

定理指出公式的充要条件为: 证明: 常用卷积

例题

又到了喜闻乐见的例题环节

YY的GCD

YY的GCD

求: 推柿子Time:

其中预处理参见上面的卷积计算。

代码略。

Crash的数字表格

Crash的数字表格

求: 推柿子(害怕.jpg)

原式等同于 枚举 记函数 。则 其中求出,前面可预处理前缀和。

答案为

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#define int long long
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]约数个数和

[SDOI2015]约数个数和

其中的约数个数。

有一个公式 带入柿子 原式等于 最后两个括号可以运用整除分块预处理。

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#define int long long
using namespace std;

int p[60000] ,cnt;
int mu[60000] ,sum[60000];
bool vis[60000];
int f[60000];//答案中两个大括号预处理
void init(){
mu[1]=1;
for(int i=2;i<=50000;i++){
if(!vis[i]){
p[++cnt]=i;
mu[i]=-1;
}
for(int j=1;j<=cnt&&p[j]*i<=50000;j++){
vis[p[j]*i]=1;
if(i%p[j]==0)break;
mu[p[j]*i]=-mu[i];
}
}
for(int i=1;i<=50000;i++)
sum[i]=sum[i-1]+mu[i];
for(int i=1;i<=50000;i++)
for(int j=1,j2;j<=i;j=j2+1){
j2=i/(i/j);
f[i]+=(j2-j+1)*(i/j);
}
}
main()
{
init();
int t;
cin >> t;
while(t--){
long long n ,m;
cin >> n >> 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+=(sum[j]-sum[i-1])*f[n/i]*f[m/i];
}
cout << ans << endl;
}
}

平方因子

求小于的无平方因子的数的个数。

这一道题表现了莫比乌斯函数真正意义

由莫比乌斯函数定义明显可以得到

对于质数,对于满足对答案无贡献,这样的数有个。

但这样减去会导致多减去如的数,会减去两次,需加回来。

可用容斥原理解。

  • 如果个不同素数的乘积,它对答案的贡献为

  • 如果有平方因子,它对答案无贡献。

可以发现容斥系数恰好是莫比乌斯函数。

答案为 莫比乌斯反演本身可以看作对整除关系的容斥。

总结

以Crash的数字表格为例,总结莫比乌斯反演套路。 套路: 优先枚举

套路: 等价于

套路: 套用莫比乌斯函数性质

套路: 优先枚举 记函数 套路: 设数转换

。则 总的来说,套性质,往前提式子,能数论分块预处理就预处理。