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 |
请登录
|