【笔记】简单数论函数集合

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);
}