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