Problem D: 欧拉函数
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$238$ |
正确数量 |
$198$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
数论 |
当前分类(单击移除)：
数论
单击选择分类：
给定一个大于$1$，不超过$2000000$的正整数$n$，输出欧拉函数，$\phi(n)$的值。
如果你并不了解欧拉函数，那么请参阅提示。
在给定的输入文件中进行读入：
一行一个正整数$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类型上界，可通过调整公式各项的计算顺序避免(比如先做除法)!