[POJ2407]欧拉函数的值

原题

题目描述

给定整数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)$

所以，我们就得出了欧拉计算函数。

源代码