選自《洛谷深入淺出進階篇》——歐拉函數+歐拉定理+擴展歐拉定理

歐拉函數：

歐拉函數定義： $\psi \left ( n \right ) =$ ?1~n中與n互質的數的個數。比如? $\psi \left ( 12 \right ) = 4$ ? ??
歐拉函數是積性函數：（也就是）當 n與m互質的時候：? $\psi \left ( nm \right ) = \psi \left (n \right ) \psi \left(m \right )$
由算術基本定理，我們可以設n= $\prod_{i=1}^{m} p_{i}^{k_{i}}$ ，那么我們只要計算出 $\psi \left(p_{i}^{k_{i}} \right )$ 的取值就能求出 $\psi \left(n \right )$ 的取值。下面給出證明

$\psi \left(p_{i}^{k_{i}} \right )$ 的取值怎么求？也就是求1~ $p_{i}^{k_{i}}$ 中與 $p_{i}^{k_{i}}$ 互質的數的個數

我們可以求與 $p_{i}^{k_{i}}$ 不互質的數的個數，由于p是質數，所以與 $p_{i}^{k_{i}}$ 不互質的數一定是p的倍數

那么1~ $p_{i}^{k_{i}}$ 中，p的倍數就是? $\frac{p_{i}^{k_{i}}}{p}=p_{i}^{k_{i}-1}$ , 那么我們就知道與 $p_{i}^{k_{i}}$ 不互質的數的個數就是 $p_{i}^{k_{i}}-$ $p_{i}^{k_{i}-1 }$ 。也就是? $p_{i}^{k_{i}}\left(1-\frac{1}{p} \right )$

由于 $p_{i}^{k_{i}}$ 之間互質，且歐拉函數是一個積性函數，那么有

$\psi \left(n\right) = \prod_{i=1}^{m} \psi \left( p_{i}^{k_{i}} \right ) =\left(\prod_{i=1}^{m} p_{i}^{k_{i}} \right)\cdot \left(\prod_{i}^{m}\left(1-\frac{1}{p}\right)\right)=n\cdot \prod_{i}^{m}\left(1-\frac{1}{p} \right)$

所以我們只需要求出n的所有質因子p，然后求出 $1-\frac{1}{p}$ ?的乘積即可?

phi = n;
for(int i=2 ; i*i<=n ; i++ )if( n%i == 0 ){phi = phi/i * (i-1 )   // 1- 1/p == (p-1)/p 為了防止爆int，故意不寫成phi*(i-1)/iwhile ( n%i==0 ) n/=i ;}
if(n!=1) phi =phi/n *(n-1);  //防止n有一個大于 sqrt（n）的質因子的情況

以上就是歐拉函數的板子，請牢牢記住，后面回經常用到。

歐拉定理：對于正整數a，n，若a $\perp$ n，則 $a^{\psi\left(n\right)}\equiv 1 \left(mod \ n \right )$

擴展歐拉定理：

對于正整數a，n，始終有? $a^{\psi \left(n \right )}\equiv a^{k\psi \left(n \right )}\left(mod\ n \right ),k\epsilon N_{+}$

那么對于任意的正整數a，k，n ，當k大于? $\psi\left(n \right )$ 時，

$a^{k} \equiv a^{k\ mod \ \psi\left(n \right )+\psi\left(n \right )}\left(mod\ n \right )$

對于這些定理，此處不加以證明，背過即可。

下面給出一些例題，用來了解一些歐拉函數在算法競賽中的應用

（緩慢更新中）

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/207444.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/207444.shtml
英文地址，請注明出處：http://en.pswp.cn/news/207444.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！