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

开始恶补数学

数论函数

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

积性函数

且

例子：

除数函数

除数函数用来表示的因子的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的数字表格为例，总结莫比乌斯反演套路。 套路: 优先枚举

套路: 等价于

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

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

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