积性函数
对于一个离散函数$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
|
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;
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;
}
|
