原:冷静分析「欧拉函数φ」 偶然找到好久之前遗失的板子 积性函数线性筛.cpp 所以干脆作个总结。 这些数论函数在中学竞赛中算是非常基础的知识了,其简单的性质也就不做赘述了。 下方百科链接: - 莫比乌斯函数-百度百科 - 欧拉函数-百度百科 - 因数个数函数-百度百科 - 因数和函数-百度百科

莫比乌斯函数μ

相关狄利克雷卷积 e(n)=dnμ(d)e=μ1e(n)=\sum_{d\mid n}\mu(d)\quad\Leftrightarrow\quad e=\mu*1

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
namespace Mobius_Table {
int cnt=0, prime[N], vis[N], mu[N];
int t;
vis[1] = mu[1] = 1;
for(int i=2;i<=N;++i) {
if(!vis[i])
prime[++cnt] = i, mu[i] = -1;

for(int j=1;j<=cnt&&(t=prime[j]*i)<=N;++j)
{
vis[t] = 1;
if(i%prime[j]==0) { mu[t] = 0;break;}
else mu[t] = -mu[i];
}
}
} //μ

前缀和筛法

考虑构造函数 ggSS 表示前缀和。其中 表示函数 ff 和函数 gg 的狄利克雷卷积。

以上为基本套路...... 我们取函数 ggg(x)=1g(x)=1

1
2
3
4
5
6
7
8
9
10
11
12
#include <map>
map<int, ll> map;
long long solve(int n) {
if(n <= N) return mu[n];
if(map[n]) return map[n];
int r; long long res=0;
for(int l=2;l<=n;l=r+1) {
r = n/(n/l);
res += 1ll*(r-l+1)*solve(n/l);
}
return map[n]=1-res;
}

欧拉函数φ

特殊性质

n=dnϕ(d)n=\sum_{d|n}\phi(d) 一个有意思的证明

线性筛:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
namespace Phi_Table {
int cnt=0, prime[N], vis[N], phi[N];
int t;
vis[1] = phi[1] = 1;
for(int i=2;i<=N;++i) {
if(!vis[i])
prime[++cnt] = i, phi[i] = i-1;

for(int j=1;j<=cnt&&(t=prime[j]*i)<=N;++j)
{
vis[t] = 1;
if(i%prime[j]==0) { phi[t] = phi[i]*prime[j];break;}
else phi[t] = (prime[j]-1)*phi[i];
}
}
} //φ

前缀和筛法:

考虑构造函数 ggSS 表示前缀和。其中 表示函数 ff 和函数 gg 的狄利克雷卷积。

构造函数 g(x)=1g(x)=1, 则有

S(n)=n(n+1)2i=2nS([ni])S(n)=\frac{n(n+1)}{2}-\sum_{i=2}^{n}S([\frac{n}{i}])
1
2
3
4
5
6
7
8
9
10
11
12
#include <map>
map<int, ll> map;
long long solve(int n) {
if(n <= N) return phi[n];
if(map[n]) return map[n];
int r; ll res=0;
for(int l=2;l<=n;l=r+1) {
r = n/(n/l);
res += 1ll*(r-l+1)*solve(n/l);
}
return map[n]=1ll*n*(n+1)/2-res;
}

约数个数函数d

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
namespace Divisors_Number_Table {
int cnt=0, prime[N], vis[N];
int Min_Divnum[N], d[N];
int t;
for(int i=2;i<=N;++i) {
if(!vis[i])
prime[++cnt] = i, d[i] = 2, Min_Divnum[i] = 1;

for(int j=1;j<=cnt&&(t=prime[j]*i)<=N;++j)
{
vis[t] = 1;
if(i%prime[j]==0) {
Min_Divnum[t] = Min_Divnum[i]+1;
d[t] = d[i]/(Min_Divnum[i]+1)*(Min_Divnum[i]+2);
break;
}
else Min_Divnum[t] = 1, d[t] = 2*d[i];
}
}
} //d

约数和函数σ

线性筛

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
namespace Divisors_Sum_Table {
typedef long long LL;
int cnt=0, prime[N], vis[N];
LL f[N], Min_Fac_last[N], Min_Fac_sum[N];
for(int i=2;i<=N;++i) {
if(!vis[i]) {
Min_Fac_last[i] = prime[++cnt] = i;
f[i] = Min_Fac_sum[i] = i+1;
}

for(int j=1;j<=cnt&&(t=prime[j]*i)<=N;++j)
{
vis[t] = 1;
if(i%prime[j]==0) {
Min_Fac_last[t] = Min_Fac_last[i]*prime[j];
Min_Fac_sum[t] = Min_Fac_sum[i]+Min_Fac_last[t];
f[t] = f[t]/Min_Fac_sum[i]*Min_Fac_sum[t];
break;
}
else {
Min_Fac_last[t] = prime[j];
Min_Fac_sum[t] = prime[j]+1;
f[t] = f[i]*(prime[j]+1);
}
}
}
} //σ