歐拉函數

代碼以後再補

歐拉函數

我們用$\phi(n)$表示歐拉函數

定義：$\phi(n)$表示對於整數$n$,小於等於$n$中與$n$互質的數的個數

性質

1.$\phi(n)$為積性函數

2.$\sum_{d|n}\phi(d)=n$

3.$1$到$n$中與$n$互質的數的和為$n*\dfrac{\phi(n)}{2}(n>1)$

計算方法

假設我們需要計算$\phi(n)$

分情況討論

1.當$n=1$時

很明顯，答案為$1$

2.當$n$為質數時

根據素數的定義,答案為$n-1$

(僅有$n$與$n$不互質)

3.當$n$為合數時

我們已經知道了$n$為素數的情況

不妨對$n$進行質因數分解

設$n=a_1^{p_1}*a_2^{p_2}...*a_k^{p_k}$

假設$k=1$

那麼$\phi(p^k)=p^k-p^{k-1}$

證明:

考慮容斥，與一個數互素的數的個數就是這個數減去與它不互素的數的個數

因為$p$是素數，所以在$p^k$中與其不互素的數為$1*p$,$2*p$....$p^{k-1}*p$,有$p^{k-1}$個

得證

當$k\neq 1$時

$$\phi(n)$$

$$=\varphi \left( a^{p_{1}}_{1}a^{p_{2}\ldots }_{2}a^{Pk}_{k}\right)$$

$$=\prod ^{k}_{i=1}a^{P_i}-a^{P_{i}-1}_{i}$$

$$=\prod ^{k}_{i=1}a^{Pi}_{i}(1-\dfrac {1}{p_{i}})$$

$$=n*\prod ^{k}_{i=1}(1-\dfrac {1}{p_{i}})$$

4.Euler篩法

因為歐拉函數是積性函數

因此可以使用線性篩法