数论函数

发表于 更新于 分类于 阅读次数： Disqus：

莫比乌斯函数

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
#include<bits/stdc++.h>
using namespace std;
int T;
int prime[50001];
int tot;
bool b[50001];
int pr[50001];
inline void prepare_pr()
{
	pr[1]=1;
	for(register int i=2;i<=50000;i++)
	{
		if(!b[i])
		{
			prime[++tot]=i;
			pr[i]=-1;
		}
		for(register int j=1;j<=tot&&i*prime[j]<=50000;j++)
		{
			if(i%prime[j])
			{
				b[i*prime[j]]=1;
				pr[i*prime[j]]=-pr[i];
			}
			else
			{
				b[i*prime[j]]=1;
				pr[i*prime[j]]=0;
				break;
			}
		}
	}
	return ;
}

欧拉函数

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
int prime[50001];
int tot;
bool b[50001];
int phi[50001];
inline void prepare_phi()
{
	phi[1]=1;
	for(register int i=2;i<=50000;i++)
	{
		if(!b[i])
		{
			prime[++tot]=i;
			phi[i]=i-1;
		}
		for(register int j=1;j<=tot&&i*prime[j]<=50000;j++)
		{
			if(i%prime[j])
			{
				b[i*prime[j]]=1;
				phi[i*prime[j]]=phi[i]*phi[prime[j]];
			}
			else
			{
				b[i*prime[j]]=1;
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
		}
	}
	return ;
}