Problem 1712 --欧拉函数1712: 欧拉函数
| 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类型上界，可通过调整公式各项的计算顺序避免(比如先做除法)!
| 本题记录 |
用 户（点击查看用户） |
运行号（点击购买题解） |
时 间 |
| 算法最快[$0 $ms]
|
Metro
|
857637
|
2022-05-17 16:35:00 |
| 内存最少[$0 $KB]
|
yaoking
|
614520 |
2020-10-06 16:22:02 |
| 第一AC |
计爱玲 |
146045
|
2017-11-08 15:03:48 |
| 第一挑战 |
计爱玲
|
146025 |
2017-11-08 14:42:56 |
| 竞赛编号 |
竞赛名称 |
竞赛时间 |
访问比赛 |
| 1793 |
2023年第15届蓝桥杯全国软件和信息技术专业人才大赛_安徽科技学院校赛 |
2023-12-10 14:00:00 |
请登录
|
| 1755 |
2022-2023-2学期<计算机专业竞赛实训> 第11周练习： 数论,博弈,矩阵【21计算机12345】 |
2023-04-28 08:00:00 |
请登录
|
| 1691 |
2021-2022-2学期<算法分析与设计> 第12周练习：数论算法 |
2022-05-06 00:00:00 |
请登录
|
| 1548 |
2020《图灵信息学算法》高级班第2-3单元:数论和组合数学 |
2020-10-04 09:00:00 |
请登录
|
| 1343 |
ACM中级算法：数论素数 |
2019-05-11 19:00:00 |
请登录
|