原題

題目描述

給定整數(shù)n，求n的歐拉函數(shù)的值

輸入

多組數(shù)據(jù) 每行一個(gè)整數(shù)，表示n( 1 <= n <= 1,000,000,000) 一個(gè)0，表示輸入結(jié)束

輸出

每行輸入一個(gè)整數(shù)，表示對(duì)應(yīng)的n的歐拉函數(shù)值

樣例輸入

7 12 0

樣例輸出

6 4

分析

要解決這道題，我們先來(lái)了解什么是歐拉函數(shù)和歐拉定理。

歐拉函數(shù)φ$φ$：不超過(guò)n的且與n互質(zhì)的正整數(shù)的個(gè)數(shù)。 如果n為素?cái)?shù)p，則φ(p)=p?1$φ(p)=p-1$ 如果n為素?cái)?shù)p的冪次pa$p^a$，則φ(pa)=(p?1)?pa?1$φ(p^a)=(p-1)*p^a-1$. 歐拉函數(shù)為積性函數(shù)：如果n為任意兩個(gè)互質(zhì)的數(shù)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互質(zhì)，則aφ(m)≡1(mod m)$a^{φ(m)}/equiv 1(mod / m)$

所以，我們就得出了歐拉計(jì)算函數(shù)。

源代碼