定义

数论函数(arithmetic function)

定义

  • 在数论上, 算术函数(或称数论函数)指定义域为正整数、陪域为复数的函数

积性函数(multiplicative function)

定义

  • 若$(m,n)=1$, 有$f(mn)=f(m)f(n)$, 称数论函数$f(n)$为积性函数;
    若对任意正整数$m,n$, 都有$f(mn)=f(m)f(n)$, 则称数论函数$f(n)$为完全积性函数

性质1

  • 设$f(n)$是积性函数, 并且$n=p_1^{a_1}p_2^{a_2}\cdots p_s^{a_s}$是$n$的质因数分解形式, 那么$f(n)=\prod_{i=1}^{s}{f(p_i^{a_i})}$. 特别的如果$f(n)$是完全积性函数, $f(n)=\prod_{i=1}^{s}{f(p_i)^{a_i}}$

性质2

  • 设$f(n), g(n)$是两个积性函数, 那么$(fg)(n)=f(n)g(n),(f/g)(n)=\frac{f(n)}{g(n)}$也是积性函数

性质3

  • 定义$F(n) = \sum_{d|n}{f(d)}$称为$f$的和型函数(summatory function)
  • 如果$f(n)$是积性函数, 那么$F(n)$也是积性函数

性质4

  • 假设$f(n), g(n)$是两个数论函数, 那么以下形式称为$f$和$g$的狄利克雷卷积(Dirichlet product or Dirichlet convolution)$$(f * g)(n)=\sum_{d|n}{f(d)g(n/d)}$$
  • 如果$f(n), g(n)$是积性函数, 那么$(f * g)(n)$也是积性函数

性质5

  • 对于任意积性函数$f$,$f(1) = 1$

线性筛

  • 素数定理 $\pi(x)$表示不超过x的素数 $\pi(x) \text{~} \frac{x}{ln(x)}$

两种筛法

Eratosthenes筛法 $O(nlog(log(n)))$

1
2
3
4
5
6
int tot=0;
primes[tot++]=2;
for(int i=3;i<maxn;i+=2) if(!vis[i]){
primes[tot++]=i;
for(int j=i+i;j<maxn;j+=i) vis[i]=1;
}

Euler筛法 $O(n)$

  • 每个数只会被其最小的质因子筛去
  • 由于积性函数的性质,$p$为质数
    已知$f(p),f(p^k)$表达式,即可用筛法预处理所有的$f$
1
2
3
4
5
6
7
8
9
10
int tot=0;
for(int i=2;i<maxn;++i){
if(!vis[i]) primes[tot++]=i;
for(int j=0;j<tot;++j){
int t=i*primes[j];
if(t>maxn) break;
vis[t]=1;
if(i%primes[j]==0) break;
}
}

Euler函数

性质

  • $\phi(n)$表示1..n中与n互质的整数个数
    $$\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_k})$$
  • $\sum_{d|n}\phi(d)=n$
  • n>1时,1..n中与n互质的整数和为$n\phi(n) \over 2$
  • $\phi(n/g) = \sum_{i=1}^n [(n,i) = g]$ (g为n的因子)

定义求Euler函数

1
2
3
4
5
6
7
8
9
10
11
12
int Euler_phi(int n){
int res=n;
for(int i=2;i*i<=n;++i){ //或者预处理出质因子
if(n%i==0){
res=res/i*(i-1);
while(n%i==0) n/=i;
}
if(n<=1) break;
}
if(n>1) res*=res/n*(n-1);
return res;
}

线性筛求Euler函数

  • 设$p$为质数,则$\phi(p) = p-1$,$\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$
  • 因此当$i \equiv 0 \pmod p$,$\phi(i*p) = \phi(i)*p$,否则$\phi(i*p) = \phi(i)*(p-1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Euler(){
memset(vis,0,sizeof vis);
int tot=0;phi[1]=1;
for(int i=2;i<maxn;++i){
if(!vis[i]){
primes[tot++]=i;
phi[i]=i-1;
}
for(int j=0;j<tot;++j){
int t=i*primes[j],p=primes[j];
if(t>maxn) break;
vis[t]=1;
if(i%p==0){
phi[t]=phi[i]*p;
break;
}
else phi[t]=phi[i]*(p-1);
}
}
}

Möbius反演

参考