Загрузка [MathJax]/jax/output/HTML-CSS/jax.js
Sign in
or
Register
Courses
Textbook
Compiler
Contests
Topics
Courses
算術
欧拉函数和数论中的其他问题
Module:
欧拉函数和数论中的其他问题
Problem
1
/9
欧拉函数
Theory
Click to read/hide
欧拉函数
该理论可以在
此处
阅读。
Problem
给定一个自然数
n
<=
10
9
,
求小于
\的自然数个数(n\ )
与
n
互质。这个数字用
f
(
n
)
表示,称为 Euler 的 phi 函数。算法的复杂度应该是
O
(
√
n
)
.
输入
输入是一个自然数
n
。
印记
打印问题的答案。
例子
<头> <正文>
1000
ms
256 Mb
Rules for program design and list of errors in automatic problem checking
Teacher commentary
#
输入
输出
1
2
1