H:欧拉函数

Problem H: 欧拉函数

Time Limit

$1$ 秒/Second(s)

Memory Limit

$512$ 兆字节/Megabyte(s)

提交总数

$238$

正确数量

$198$

裁判形式

标准裁判/Standard Judge

我的状态

尚未尝试

难度

分类标签

数论

给定一个大于

$1$ ，不超过

$2000000$ 的正整数

$n$ ，输出欧拉函数，

$\phi(n)$ 的值。
如果你并不了解欧拉函数，那么请参阅提示。

提示

欧拉函数

$\phi(n)$ 是数论中非常重要的一个函数，其表示

$1$ 到

$n$ 之间，与

$n$ 互质的数的个数。显然的，我们可以通过定义直接计算

$\phi(n)$ 。当然，

$\phi(n)$ 还有这么一种计算方法。首先我们对n进行质因数分解，不妨设

$n={p_1}^{a_1} * {p_2}^{a_2} * ... *{p_k}^{a_k}$ （这里

$a^b$ 表示

$a$ 的

$b$ 次幂，

$p_1$ 到

$p_k$ 为

$k$ 个互不相同的质数，

$a_1$ 到

$a_k$ 均为正整数），那么

$\phi(n)=n(1-(1/p_1))(1-(1/p_2))....(1-(1/p_k))$ 稍稍化简一下就是

$\phi(n)=n(p_1-1)(p_2-1)...(p_k-1)/(p_1*p_2*...*p_k)$ 计算的时候小心中间计算结果超过int类型上界，可通过调整公式各项的计算顺序避免(比如先做除法)!

Problem H: 欧拉函数