原題

題目描述

給定整數n，求n的歐拉函數的值

輸入

多組數據 每行一個整數，表示n( 1 <= n <= 1,000,000,000) 一個0，表示輸入結束

輸出

每行輸入一個整數，表示對應的n的歐拉函數值

樣例輸入

7 12 0

樣例輸出

6 4

分析

要解決這道題，我們先來了解什么是歐拉函數和歐拉定理。

歐拉函數φ$φ$：不超過n的且與n互質的正整數的個數。 如果n為素數p，則φ(p)=p?1$φ(p)=p-1$ 如果n為素數p的冪次pa$p^a$，則φ(pa)=(p?1)?pa?1$φ(p^a)=(p-1)*p^a-1$. 歐拉函數為積性函數：如果n為任意兩個互質的數a、b的積，則φ(n)=φ(a)?φ(b)$φ(n)=φ(a)*φ(b)$

n=p1a1?p2a2?……?pkak${p_1}^{a1}*{p_2}^{a2}*……*{p_k}^{ak}$ 則φ(n)=n?(1?1/p1)?(1?1/p2)?……?(1?1/pk)$φ(n)=n*(1-1/p_1)*(1-1/p_2)*……*(1-1/p_k)$

歐拉定理： 若a與m互質，則aφ(m)≡1(mod m)$a^{φ(m)}/equiv 1(mod / m)$

所以，我們就得出了歐拉計算函數。

源代碼