积性函数

对于一个离散函数$f(x), x\in Z^+$ , 如果$\forall \gcd(a,b)=1$都有$f(a\cdot b)=f(a)\cdot f(b)$, 则称函数$f(x)$为积性函数。

完全积性函数

对于一个离散函数$f(x), x\in Z^+$ , 如果$\forall a,b\in Z^+$都有$f(a\cdot b)=f(a)\cdot f(b)$, 则称函数$f(x)$为完全积性函数。

积性函数分析

我们根据积性函数的定义,其实只要我们计算出了所有素数的幂的函数值,则任何其他$f(x)$都可以快速获取。

对此笔者准备了一个模版,我们只需要修改其中的56到63行即可

欧拉函数

$\phi(n)$就是小于等于n,且与n互质的数的个数。

1
2
3
4
5
6
7
8
9
10
11
12
//O(lgn)适用于少求
int euler(int n){
int ret=n;
for(int i=2; i*i<=n; i++)
if(n%i==0){
ret=ret-ret/i;
do n/=i;
while(n%i==0);
}
if(n>1)ret=ret-ret/n;
return ret;
}

莫比乌斯函数

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
//求单个值
ll getmob(ll a){
ll x=a,tmp=a;
int cnt=0,now=0;
for(ll j=2;j*j<=x;j++){
now=0;
if(x%j==0){
while(x%j==0) now++,x/=j;
if(now>1) return 0;
cnt++;
}
}
if(x!=1) cnt++;
return (cnt&1)?-1:1;
}
int getmu(int n)
{
int v=1;
for(int i=2;i*i<=n;i++)
if(n%i==0)
{
v=-v;n/=i;
if(n%i==0)return 0;
}
if(n!=1)v=-v;
return v;
}
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
#include<bits/stdc++.h>
using namespace std;

/* 数论函数表
i phi(i) PHI(i) muu(i) MUU(i) ddd(i) DDD(i) sig(i) SIG(i)
1 1 1 1 1 1 1 1 1
2 1 2 -1 0 2 3 3 4
3 2 4 -1 -1 2 5 4 8
4 2 6 0 -1 3 8 7 15
5 4 10 -1 -2 2 10 6 21
6 2 12 1 -1 4 14 12 33
7 6 18 -1 -2 2 16 8 41
8 4 22 0 -2 4 20 15 56
9 6 28 0 -2 3 23 13 69
10 4 32 1 -1 4 27 18 87
11 10 42 -1 -2 2 29 12 99
12 4 46 0 -2 6 35 28 127
13 12 58 -1 -3 2 37 14 141
14 6 64 1 -2 4 41 24 165
15 8 72 1 -1 4 45 24 189
16 8 80 0 -1 5 50 31 220
17 16 96 -1 -2 2 52 18 238
18 6 102 0 -2 6 58 39 277
19 18 120 -1 -3 2 60 20 297
20 8 128 0 -3 6 66 42 339
21 12 140 1 -2 4 70 32 371
22 10 150 1 -1 4 74 36 407
23 22 172 -1 -2 2 76 24 431
24 8 180 0 -2 8 84 60 491
25 20 200 0 -2 3 87 31 522
26 12 212 1 -1 4 91 42 564
27 18 230 0 -1 4 95 40 604
28 12 242 0 -1 6 101 56 660
29 28 270 -1 -2 2 103 30 690
30 8 278 -1 -3 8 111 72 762*/

/**** * 超级积性函数线性筛 * ****/
typedef long long ll;
const ll maxn=5e6;
ll no_pri[maxn]={0,1,0},pri[maxn],low[maxn];
ll PHI[maxn],DDD[maxn],XDX[maxn],MUU[maxn],SIG[maxn];
void f_ini(){
for(ll i=2;i<maxn;i++){
if(!no_pri[i]) low[i]=pri[++pri[0]]=i;
for(ll j=1;pri[j]*i<maxn;j++){
no_pri[pri[j]*i]=1;
if(i%pri[j]==0) {
low[pri[j]*i]=low[i]*pri[j];
break;
}
else low[pri[j]*i]=pri[j];
}
}

DDD[1]=PHI[1]=MUU[1]=SIG[1]=1;// 改这里
for(ll i=1;i<=pri[0];i++){
for(ll mul=pri[i],ct=1;mul<maxn;mul*=pri[i],ct++){
DDD[mul]=ct+1;// 改这里
SIG[mul]=SIG[mul/pri[i]]+mul;// 改这里
MUU[mul]=ct==1?-1:0;// 改这里
PHI[mul]=mul/pri[i]*(pri[i]-1);// 改这里
}
}

for(ll i=2;i<maxn;i++){
for(ll j=1;pri[j]*i<maxn;j++){
ll x=low[i*pri[j]], y=i*pri[j]/x;
DDD[x*y]=DDD[x]*DDD[y];
MUU[x*y]=MUU[x]*MUU[y];
PHI[x*y]=PHI[x]*PHI[y];
SIG[x*y]=SIG[x]*SIG[y];
if(i%pri[j]==0) break;
}
}

for(ll i=1;i<maxn;i++) {
DDD[i]+=DDD[i-1];
MUU[i]+=MUU[i-1];
PHI[i]+=PHI[i-1];
SIG[i]+=SIG[i-1];
XDX[i]=(DDD[i]-DDD[i-1])*i+XDX[i-1];
}
}

int main(){
f_ini();
printf("数论函数表\n");
printf(" i phi(i) PHI(i) muu(i) MUU(i) ddd(i) DDD(i) sig(i) SIG(i)\n");
for(ll i=1;i<=30;i++) {
printf("%2lld %3lld %6lld %6lld %6lld %6lld %6lld %6lld %6lld\n",i,PHI[i]-PHI[i-1],PHI[i],MUU[i]-MUU[i-1],MUU[i],DDD[i]-DDD[i-1],DDD[i],SIG[i]-SIG[i-1],SIG[i]);
}
return 0;
}