数论函数/莫比乌斯反演

Nannan Lv5
  2023-08-02 22:25 2023-08-02 22:25 Created   2024-09-30 19:30:23 2024-09-30 19:30:23 Updated      

数论函数/莫比乌斯反演

1.1积性函数

数论函数：可以认为是定义在整数上的函数。

1)积性函数定义

(a,b) = 1,f(a,b) = f(a)f(b)

2)积性函数性质

  1. 对于积性函数，是被所有处的值决定的,即积性函数的值完全由素数的幂次决定

    a = 1,f(b) = f(1)f(b)

​

​

​

​ 对于的话就没有办法把它表示成更小的素数幂的形式了，因为显然和不互质

  1. (重要！)积性函数积性函数还是积性函数

1.2 、完全积性函数

1)定义

f(a,b) = f(a)f(b) 不要求(a,b) = 1

1.3常见积性函数

①

②常数函数

③单位函数$$ e(x)= \tag{1} =x = 1$$

④欧拉函数

**$\phi(p^e) = (1-\dfrac{1}{p^e})p^e = p^e-p^{e-1}$*

⑤因子函数因子个数

⑥因子和

⑦莫比乌斯函数

img

1.4 莫比乌斯函数

来看一个特殊的函数：常数函数的狄拉克雷逆元，我们称其为莫比乌斯函数

  1. 莫比乌斯函数定义

有平方因子

1 2 3 4 5 6 7 8 9 10
1 -1 -1 0 -1 1 -1 0 0 1

2.莫比乌斯函数性质

1.

即 ：

人话：一个数的所有约数的莫比乌斯函数之和为这个数的单位函数

该性质是莫比乌斯反演中最重要的技巧之一。

  1. 结合和

1.5线性筛求积性函数

线性筛：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =1000010;
bool is_pri[maxn];
int pri[maxn];
int cnt;

void init(int n)
{
	memset(is_pri, true, sizeof(is_pri));
	is_pri[1] = false;
	cnt = 0;
	for (int i = 2; i <= n; i++)
	{
		if (is_pri[i])
			pri[++cnt] = i;
		for (int j = 1; j <= cnt && i * pri[j] <= n; j++)
		{
			is_pri[i * pri[j]] = false;
			if (i % pri[j] == 0)break;            
		}
	}
}

由于一个正整数(除外)可以通过质因数分解得到，对于非的正整数都有：

$n = p_1^{e_1}p_2^{e_2}…*p_k^{e_k}$

根据积性函数定义，对于一个积性函数有:


也就是说我们可以根据质因子推导出由该因子组成的合数。

对于一个合数有:

我们可以用线性筛帮助我们在求出以内的积性函数值

定义：为的最小质因子，记录当前筛出的个质数,是的值(标准分解里面的第一项)

  1. 求出.

  2. 若说明是合数，我们直接递推

    若刚好是素数幂次，一般能从推出

因子个数：

因子和：

欧拉函数：

莫比乌斯函数：$$ \mu(i)= \begin{cases} -1,\quad i= pi\ 0\end{cases} \tag{1} $$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void init(int n)//求各个函数的最小素数因子和指数
{
	p[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(!p[i])p[i] = i,pe[i] = i,pr[++cnt] = i;
		for(int j = 1;j<=cnt&&pr[j]*i<=n;j++)
		{
			p[i*pr[j]] = pr[j];
			if(p[i]==pr[j])//i和i*pr[j]的最小的素因子是一样的
             {
                //比如pe[5^3*7] = pr[5^2*7]*5
				pe[i*pr[j]] = pe[i]*pr[j];
				break;
			}
			else//说明被更小的质因子筛到了
			{
				pe[i*pr[j]] = pr[j];
			}
 		}
	} 
}

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
//写法1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =1000010;
int p[maxn],pr[maxn/5],pe[maxn];
int cnt;

void init(int n)//求各个函数的最小素数因子和指数
{
	p[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(!p[i])p[i] = i,pe[i] = i,pr[++cnt] = i;
		for(int j = 1;j<=cnt&&pr[j]*i<=n;j++)
		{
			p[i*pr[j]] = pr[j];
			if(p[i]==pr[j])//i和i*pr[j]的素因子是一样的
			{
				pe[i*pr[j]] = pe[i]*pr[j];
				break;
			}
			else
			{
				pe[i*pr[j]] = pr[j];
			}
 		}
	}
}

uint f[N],a,b,ans;


void compute(int n,function<void(int)>calcpe){
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pr[i])calcpe(i);
		else f[i] = f[pe[i]]*f[i/pe[i]];//积性函数，把这两个乘起来
	}
	for(uint i = 1;i<=n;i++)
		ans ^= (a*i*f[i]+b);
	cout<<ans<<endl;
}


int main()
{
	cin>>n>>a>>b;
	init(n);

	//因子个数
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pe[i])
			f[i] = f[i/p[i]]+1;//i/p[i]==>p^{e-1}
		else f[i] = f[pe[i]]*f[i/pe[i]];//积性函数，把这两个乘起来
	}
	for(uint i = 1;i<=n;i++)
		ans ^= (a*i*f[i]+b);
	cout<<ans<<endl;

	//因子和
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pe[i])f[i] = f[i/p[i]]+i;
		else f[i] = f[pe[i]]*f[i/pe[i]];
	}
	for(uint i = 1;i<=n;i++)
		ans ^= (a*i*f[i]+b);
	cout<<ans<<endl;


	//欧拉函数
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pe[i])f[i] = i/p[i]*(p[i]-1);
		else f[i] = f[pe[i]]*f[i/pe[i]];
	}
	for(uint i = 1;i<=n;i++)
		ans ^= (a*i*f[i]+b);
	cout<<ans<<endl;

	//莫比乌斯函数
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pe[i]){
			if(i==p[i])f[i] = (uint)(-1);
			else f[i] = 0;
		}else f[i] = f[pe[i]]*f[i/pe[i]];
	}
	for(uint i = 1;i<=n;i++)
		ans ^= (a*i*f[i]+b);
	cout<<ans<<endl;
	return 0;
}

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//写法2
#include<bits/stdc++.h>
using namespace std;
const int maxn =20010000;
int p[maxn],pr[maxn/5],pe[maxn];
int cnt;

void init(int n)//求各个函数的最小素数因子和指数
{
	p[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(!p[i])p[i] = i,pe[i] = i,pr[++cnt] = i;
		for(int j = 1;j<=cnt&&pr[j]*i<=n;j++)
		{
			p[i*pr[j]] = pr[j];
			if(p[i]==pr[j])//i和i*pr[j]的素因子是一样的
			{
				pe[i*pr[j]] = pe[i]*pr[j];
				break;
			}
			else
			{
				pe[i*pr[j]] = pr[j];
			}
 		}
	}
}

//如果单求phi
int phi[maxn];
void phi(int n)
{
	p[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(!p[i])p[i] = i,phi[i] = i-1,pr[++cnt] = i;
		for(int j = 1;j<=cnt&&i*pr[j]<=n;j++)
		{
			p[i*pr[j]] = pr[j];
			if(p[i]==pr[j])
			{
				phi[i*pr[j]] = phi[i]*pr[j];
				break;
			}else{
				phi[i*pr[j]] = phi[i]*(pr[j]-1);
			}
		}
	}
}

unsigned int f[maxn],a,b,ans,n;


void compute(int n,function<void(int)>calcpe){
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pe[i])calcpe(i);
		else f[i] = f[pe[i]]*f[i/pe[i]];//积性函数，把这两个乘起来
	}
	for(int i = 1;i<=n;i++)
		ans ^= (a*(unsigned int)i*f[i]+b);
	cout<<ans<<endl;
}


int main()
{
	cin>>n>>a>>b;
	init(n);
	//因子个数
	compute(n,[&](int x){
		f[x] = f[x/p[x]] + 1;
	});

	//因子和
	compute(n,[&](int x){
		f[x] = f[x/p[x]] + x;
	});


	//欧拉函数
	compute(n,[&](int x){
		f[x] = x/p[x]*(p[x]-1);
	});

	//莫比乌斯函数
	compute(n,[&](int x){
		f[x] = x==p[x]?-1:0;
	});
	return 0;
}

2.1迪利克雷卷积

2.1.1定义

迪利克雷卷积是计算求和问题的有用工具。

设和是算术函数，记和的迪利克雷卷积为,

定义为：

卷积有什么含义呢？

给一个特别的栗子：定义恒等函数、常函数,

它们的卷积是：$(I1)(n) = \sum_{d|n}I(d)1(\dfrac{n}{d}) = \sum_{d|n}d1 = \sum_{d|n}d = \sigma(n)$

所以记：

✳常见积性函数

下面积性函数，在迪利克雷卷积中常常用到：

:单位函数，

:幂函数，

元函数，

因数和函数，

约数个数，

✳迪利克雷卷积函数

将上述数论函数两两做卷积，可以得到一些新的数论函数：

常见的例子

  1. ❗

    即,莫比乌斯函数性质

  2. ❗

    即,即一个数所有约数的欧拉函数之和为这个数

  3. 根据除数函数定义：

除数函数与幂函数

![image-20230629211009387](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230629211009387.png)

欧拉函数与恒等函数

![image-20230629211036787](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230629211036787.png)

2.1.2性质

  1. 符合交换律和结合律
  2. (重要)和是积性函数=>是积性函数

![image-20230629211140895](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230629211140895.png)

3.1莫比乌斯反演

引入

  1. 莫比乌斯函数：有平方因子

❗它有一个与欧拉函数类似的定理。

(补充：欧拉函数这个性质的证明：

若是素数，显然有.

那么对于正整数,与它不互质的数只有，故

对于素数幂次，由(1)可知

对于（显然这里只能取）

由唯一分解定理可知

)

如下:

❗莫比乌斯反演Th1

莫比乌斯函数的和函数在整数处的取值满足:

证明：

(1)对于时，显然成立。

(2)对于时，根据积性函数的定义：

因为当时，,有对于某一项

2.莫比乌斯反演

  1. 大致过程：给定一个求和柿子，对求和柿子进行变量替换、反演(交换求和顺序)等运算，最终化简为一个能在题目给定的时间范围内求解出的柿子。
  2. 核心技巧：

3.1.1形式

3.1.2莫比乌斯反演公式

❗莫比乌斯反演Th2

莫比乌斯反演公式。

若为的和函数，对任意正整数满足则有：

约数的莫比乌斯反演：
若：

则：

倍数的莫比乌斯反演：
若：
则：

❗莫比乌斯反演Th3

设是算术函数，它的和函数，它的和函数为,如果是积性函数则也是。

莫比乌斯反演不需要是积性函数。莫比乌斯反演可以将一些函数转化，从而降低计算难度。

3.1.3构造

典例：求

不妨记

任何让我们构造一个，这里我们需要用到第二组莫比乌斯反演公式。

那么是什么嘞？根据公式可知是若干个的和。记，即的上限，我们可以得到

即:

写成公式形式就是：

接下来问题就是如何求。**是满足是的倍数的数对**，显然有

3.2 例题

eg.莫比乌斯反演

题意：

给定一个函数，已知，求。

思路：

有平方因子

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1E6+10;
unsigned int A,B,C;
int n,cnt,f[N],p[N],mu[N],pr[N],g[N];
inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}
int main(){
    scanf("%d%u%u%u", &n, &A, &B, &C);
    for (int i = 1; i <= n; i++)
        f[i] = rng61();
    p[1] = 1,mu[1] = 1;
    for(int i = 2;i<=n;i++)
    {
        if(!p[i])p[i] = i,mu[i] = (unsigned int)-1,pr[++cnt] = i;
        for(int j = 1;j<=cnt&&pr[j]*i<=n;j++)
        {
            p[i*pr[j]] = pr[j];
            if(p[i]==pr[j])
            {
                mu[i*pr[j]] = 0;
                break;
            }
            else
                mu[i*pr[j]] = (unsigned int)-mu[i];
        }
    }
    //g = f*mu
    //g[n] = sum_{d|n} f[d]*mu[n/d]
    //g[n] = sum_{n = d1*d2} f[d1]*mu[d2]
    for(int d1 = 1;d1<=n;d1++)
        for(int d2 = 1;d1*d2<=n;d2++)
            g[d1*d2] += f[d1]*mu[d2];
    unsigned int ans = 0;
    for(int i = 1;i<=n;i++)ans^=g[i];
    cout<<ans<<endl;
}

法二：

eg2互质数对

题意：

组询问，每次给两个数，求有多少对满足1并且互质。

思路：

根据迪利克雷卷积

所以

根据

我们把转化为且

后面这一块用整数分块 

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10100000, M = 10000000;
int p[N],pr[N/5],n,cnt;
int mu[N],smu[N];
int main()
{
    p[1] = 1,mu[1] = 1;
    for(int i = 2;i<=M;i++)
    {
        if(!p[i])p[i] = i,mu[i] = -1,pr[++cnt] = i;
        for(int j = 1;j<=cnt&&i*pr[j]<=M;j++)
        {
            p[i*pr[j]] = pr[j];
            if(p[i]==pr[j])
            {
                mu[i*pr[j]] = 0;
                break;
            }else{
                mu[i*pr[j]] = -mu[i];
            }
        }
    }
    for(int i = 1;i<=M;i++)
        smu[i] = smu[i-1]+mu[i];
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        if(n>m)swap(n,m);
        ll ans = 0;
        //for(i~n)因为如果for(1~m)的话,n/l就已经是0了
        for(int l = 1;l<=n;l++)
        {
            int r = min(n/(n/l),m/(m/l));//在[l,r]里面n/l和m/l都是不变的
            ans += 1ll*(smu[r]-smu[l-1])*(n/l)*(m/l);
            l = r;
        }
        cout<<ans<<endl;
    }
    return 0;
}

变式

如果题目改成求且的对数

题解：现在需要求的是

变形一下可得：

eg3.gcd之和

题意：

T组询问，每次给两个数，求

思路：

用狄利克雷卷积+提取公因数+整除分块化简

所以：

更一般地：如果的求法为：

1
2
3
4
5
for (int l = 1, r; l <= min(n, m); l = r + 1)
{
    r = min(n / (n / l), m / (m / l));
    ans += (sum[r] - sum[l - 1]) * (n / l) * (m / l);
}

本题代码：

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10100000, M = 10000000;
ll p[N],pr[N/5],n,cnt;
ll phi[N],sphi[N];
int main()
{
    p[1] = 1,phi[1] = 1;
    for(int i = 2;i<=M;i++)
    {
        if(!p[i])p[i] = i,phi[i] = i-1,pr[++cnt] = i;
        for(int j = 1;j<=cnt&&i*pr[j]<=M;j++)
        {
            p[i*pr[j]] = pr[j];
            if(p[i]==pr[j])
            {
                phi[i*pr[j]] = phi[i]*pr[j];
                break;
            }else{
                phi[i*pr[j]] = phi[i]*(pr[j]-1);
            }
        }
    }
    for(int i = 1;i<=M;i++)
        sphi[i] = sphi[i-1]+phi[i];
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        if(n>m)swap(n,m);
        ll ans = 0;
        //for(i~n)因为如果for(1~m)的话,n/l就已经是0了不用算了
        for(int l = 1;l<=n;l++)
        {
            int r = min(n/(n/l),m/(m/l));//在[l,r]里面n/l和m/l都是不变的
            ans += 1ll*(sphi[r]-sphi[l-1])*(n/l)*(m/l);
            l = r;
        }
        cout<<ans<<endl;
    }
    return 0;
}

eg4.[互质集合](互质集合 - 题目 - Daimayuan Online Judge )

题意：

组询问，每次给一个数，问{}中有多少个非空子集，满足这些数的最大公约数是。输出答案对取模的结果。

思路：

说明中的每个数都是的倍数,有个，因为不能是空的，所以

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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int N = 10100000, M = 10000000;
ll p[N],pr[N/5],n,cnt;
ll mu[N],smu[N],pw[N];
int main()
{
     std::ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    p[1] = 1,mu[1] = 1;
    for(int i = 2;i<=M;i++)
    {
        if(!p[i])p[i] = i,mu[i] = -1,pr[++cnt] = i;
        for(int j = 1;j<=cnt&&i*pr[j]<=M;j++)
        {
            p[i*pr[j]] = pr[j];
            if(p[i]==pr[j])
            {
                mu[i*pr[j]] = 0;
                break;
            }else{
                mu[i*pr[j]] = -mu[i];
            }
        }
    }
    for(int i = 1;i<=M;i++)
        smu[i] = smu[i-1]+mu[i];
    pw[0] = 1;//预处理2的幂次
    for(int i = 1;i<=M;i++)
        pw[i] = pw[i-1]*2%mod ;
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        ll ans = 0;
        for(int l = 1;l<=n;l++)
        {
            ll r = n/(n/l);
            ans += 1ll*(smu[r]-smu[l-1])*(pw[n/l]-1)%mod;
            ans%=mod;
            l = r;
        }
        if(ans<0)ans+=mod;
        cout<<ans<<'\n';
    }
    return 0;
}

eg5.LCMSUM1

题意：

组询问，每次给一个，输出。

思路：

令

$=\sum_{i = 1}^{n}inf((i,n))$

$=\sum_{i = 1}^{n}in\sum_{d|n,d|i}g(d)$

因为是的因子，所以可以被整除

$ = n\sum_{d|n}g(d)\dfrac{\dfrac{n}{d}(\dfrac{n}{d}+1)}{2}$

(补充：的证明：

又因为我们知道，只在和时候有效，那么当时,当时，其他情况都是0，

那么，因为,所以)

因为是分数，我们给它配一个进去

令

即：

于是：

综上所述：

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<bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;

const int N = 10010000,M = 10000000;
int p[N],pr[N/5],n,pe[N],cnt;
u64 h[N];

void init(int n)
{
	p[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(!p[i])p[i] = i,pe[i] = i,pr[++cnt] = i;
		for(int j = 1;j<=cnt&&i*pr[j]<=n;j++)
		{
			p[i*pr[j]] = pr[j];
			if(p[i]==pr[j])
			{
				pe[i*pr[j]] = pe[i]*pr[j];
				break;
			}
			else
			{
				pe[i*pr[j]] = pr[j];
			}
		}
	}

}

int main()
{
	init(M);
	h[1] = 1;
	for(int i = 2;i<=M;i++)
	{
		if(i==pe[i])h[i] = h[i/p[i]]+(u64)i*(i-i/p[i]);
		else h[i] = h[pe[i]]*h[i/pe[i]];
	}
	int T;
	cin>>T;
	for(int i =1;i<=T;i++)
	{
		int n;
		cin>>n;
		u64 ans = n*(1+h[n])/2;
		cout<<ans%(1ull<<60)<<endl;
	}
	return 0;
}

eg6.LCMSUM2

题意：

组询问，每次给两个数，求。

思路：

令，这里还是数论函数，因为对于数论函数我们只要求定义域是整数

那么:

$ = \sum_{i = 1}^{n}\sum_{j = 1}^{m} ijf((i,j))$

于是：

是积性的，是积性的，那么乘起来也是积性的，对于积性函数我们只用考虑素数幂次是多少

写法一，先求素数幂次：

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
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;
const int N =10000010,M = 10000000;
int p[N],pr[N/5],pe[N];
int cnt;
int f[N],a,b,ans;
u64 h[N];

void init(int n)//求各个函数的最小素数因子和指数
{
	p[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(!p[i])p[i] = i,pe[i] = i,pr[++cnt] = i;
		for(int j = 1;j<=cnt&&pr[j]*i<=n;j++)
		{
			p[i*pr[j]] = pr[j];
			if(p[i]==pr[j])//i和i*pr[j]的素因子是一样的
			{
				pe[i*pr[j]] = pe[i]*pr[j];
				break;
			}
			else
			{
				pe[i*pr[j]] = pr[j];
			}
 		}
	}
}

int main()
{
	init(M);
	h[1] = 1;
	for(int i = 2;i<=M;i++)
	{
		if(i==pe[i])h[i] = i-(u64)i*p[i];//h(p^e) = p^e(1-p)
		else h[i] = h[pe[i]]*h[i/pe[i]];//合数，递推
	}
	for(int i = 1;i<=M;i++)h[i] += h[i-1];
	int T;
	cin>>T;

	while(T--)
	{
		int n,m;
		cin>>n>>m;
		if(n>m)swap(n,m);
		u64 ans = 0;
		for(int l = 1;l<=n;l++)
		{
			int d1 = n/l,d2 = m/l;
			int r = min(n/d1,m/d2);
			ans += (h[r]-h[l-1])*d1*(d1+1)*d2*(d2+1)/4;
			l = r;
		}
		cout<<ans%(1ull<<60)<<endl;
	}
	return 0;
}

写法二：

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
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;
const int N =10000010,M = 10000000;
int p[N],pr[N/5];
int cnt;
int f[N],a,b,ans;
u64 h[N];

int main()
{
	
	h[1] = 1;
	p[1] = 1;
	for(int i = 2;i<=M;i++)
	{
		if(!p[i])p[i] = i,h[i] = i*(u64)(1-i),pr[++cnt] = i;
		for(int j = 1;j<=cnt&&pr[j]*i<=M;j++)
		{
			p[i*pr[j]] = pr[j];
			if(p[i]==pr[j])
			{
				h[i*pr[j]] = h[i]*pr[j];
				break;
			}
			else
			{
				h[i*pr[j]] = h[i]*pr[j]*(1-pr[j]);
			}
		}
	}
	for(int i = 1;i<=M;i++)h[i] += h[i-1];
	int T;
	cin>>T;

	while(T--)
	{
		int n,m;
		cin>>n>>m;
		if(n>m)swap(n,m);
		u64 ans = 0;
		for(int l = 1;l<=n;l++)
		{
			int d1 = n/l,d2 = m/l;
			int r = min(n/d1,m/d2);
			ans += (h[r]-h[l-1])*d1*(d1+1)*d2*(d2+1)/4;
			l = r;
		}
		cout<<ans%(1ull<<60)<<endl;
	}
	return 0;
}

✳总结做题技巧

引用链接：莫比乌斯反演 - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/599151459 ))

4.杜教筛

常用于求数论函数前缀和

假设是一个积性函数，假如我们能找到另一个积性函数,使得和的前缀和都能比较快求得，那么便可以使用杜教筛求解的前缀和。

设的前缀和为,由于

等式右边交换求和顺序得到

即：

把第一项提取出来，移向后得到：

后半部分用整数分块，递归求得。前面的一般可以

杜教筛 = 整数分块+迪利克雷卷积+线性筛

时间复杂度:

公式：

对于函数 构造出来满足

常见构造：

  1. ，即
  2. ，即

杜教筛 - OI Wiki

![image-20230802154941330](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230802154941330.png)

P4213 【模板】杜教筛（Sum) 

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
const int  N  = 6000000;
typedef long long ll;
using namespace std;

bool vis[N+10];
int mu[N+10],sum1[N+10],phi[N+10];
ll sum2[N+10];
int cnt,pri[N+10];
map<int,ll>sumphi;
map<int,int>summu;

void init(int maxn)
{
    phi[1] = mu[1]=1;
    vis[0] = vis[1] = 1;
    for(int i=2;i<maxn;i++)
    {
        if(!vis[i])
        {
            pri[++cnt]=i;
            mu[i]=-1;phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&pri[j]*i<=maxn;j++)
        {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
            	mu[i*pri[j]] = 0;
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            else mu[i*pri[j]]=-mu[i],phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
    for(int i=1;i<maxn;i++)
    	sum1[i]=sum1[i-1]+mu[i],sum2[i]=sum2[i-1]+phi[i];
}
ll dlsmu(int x)
{
    if(x<N)return sum1[x];
    if(summu[x])return summu[x];
    int &ans = summu[x];
    ans+=1;
    for(ll l=2;l<=x;l++)
    {
        ll d = x/l,r=x/d;
        ans-=(r-l+1)*dlsmu(d);
        l = r;
    }
    return ans;
}
ll dlsphi(int x)
{
    if(x<N)return sum2[x];
    if(sumphi[x])return sumphi[x];
    ll &ans = sumphi[x];
    ans += x*((ll)x+1)/2;
    for(ll l=2;l<=x;l++)
    {
        ll d = x/l,r=x/d;
        ans-=(r-l+1)*dlsphi(d);
        l = r;
    }
    return ans;
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t,n;
    cin>>t;
    init(N);
    while(t--)
    {
        cin>>n;
       cout<<dlsphi(n)<<" "<<dlsmu(n)<<"\n";
    }
    return 0;
}

/*
10
2147483647
2147483646
2147483645
2147483644
2147483643
2147483642
2147483641
2147483640
2147483647
114514

*/
  • Title: 数论函数/莫比乌斯反演
  • Author: Nannan
  • Created at : 2023-08-02 22:25:00
  • Updated at : 2024-09-30 19:30:23
  • Link: https://redefine.ohevan.com/2023/08/02/八、数论函数and莫比乌斯反演/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
数论函数/莫比乌斯反演
  1. 数论函数/莫比乌斯反演
    1. 1.1积性函数
      1. 1)积性函数定义
      2. 2)积性函数性质
  2. 1.2 、完全积性函数
  3. 1.3常见积性函数
  4. 1.4 莫比乌斯函数
  5. 1.5线性筛求积性函数
  6. 2.1迪利克雷卷积
    1. 2.1.1定义
    2. ✳常见积性函数
    3. ✳迪利克雷卷积函数
    4. 2.1.2性质
  7. 3.1莫比乌斯反演
    1. 引入
    2. 2.莫比乌斯反演
    3. 3.1.1形式
    4. 3.1.2莫比乌斯反演公式
    5. 3.1.3构造
  8. 3.2 例题
    1. ✳总结做题技巧
  9. 4.杜教筛