【笔记】简单数论函数集合
Intro
咕了一年的集合。NOIp 内容。
(实际上只讲了两个函数)
常见数论函数
- $\epsilon(n)=[n=1]$
- $1(n)=1$
- $id_k(n)=n^k$
- $I(n)=id_1(n)=n$
- $\sigma_k(n)=\sum\limits_{d|n}d^k$
- $\varphi(n)$
- $\mu(n)$
欧拉函数 $\varphi(n)$
Definition
$\varphi(n)$ 等于小于等于 $n$ 且与 $n$ 互质的正整数个数,即
$$\varphi(n)=\sum\limits_{i=1}^n[\gcd(n,i)=1]$$
Property
- 不完全积性函数
- $\varphi(p)=p-1$
- $\varphi(p^k)=\varphi(p)\times p^{k-1}$
Corollary
- $\varphi(n)=n\prod\limits_{p|n}\dfrac{p-1}{p}$
- 设 $n=\prod\limits_{i=1}^kp_i^{e_i}$,则有 $$\varphi(n)=\sum\limits_{S\in{ p_1,p_2,\cdots,p_k}}(-1)^{|S|}\dfrac{n}{\prod\limits_{i\in S}i}$$
莫比乌斯函数 $\mu(n)$
Definition
$$\mu(n)=\begin{cases}(-1)^k& n=\prod\limits_{i=1}^kp_i \\ 0& \text{Otherwise}\end{cases}$$
Property
- 不完全积性函数
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e7+1;
bitset<maxn>vis;
int mu[maxn],ph[maxn];
int pr[maxn],top;
// vis: 质数判断
// mu: ,ph:
void init(int n){
ph[1]=mu[1]=1;
for (int i=2;i<=n;++i){
if (!vis[i]) pr[++top]=i,mu[i]=-1,ph[i]=i-1;
for (int j=1;j<=top&&i*pr[j]<=n;++j){
vis[i*pr[j]]=1;
if (i%pr[j]){
ph[i*pr[j]]=ph[i]*ph[pr[j]];
mu[i*pr[j]]=-mu[i];
}
else{
ph[i*pr[j]]=ph[i]*pr[j];
break;
}
}
}
}
void build_ph(int n){
for (int i=1;i<=n;++i)
ph[i]=i;
for (int i=2;i<=n;++i)
if (ph[i]==i)
for (int j=i;j<=n;j+=i)
ph[j]=ph[j]/i*(i-1);
}
int main(){
init(your_range);
build_ph(your_range);
}