Module: 欧拉函数和数论中的其他问题


Problem

1 /9


欧拉函数

Theory Click to read/hide

欧拉函数

该理论可以在此处阅读。

Problem

给定一个自然数\(n <= 10^9,\)求小于 \的自然数个数(n\ ) 与 \(n\)互质。这个数字用 \( f(n) \) 表示，称为 Euler 的 phi 函数。算法的复杂度应该是 \( O(\sqrt{n})\) .

输入
输入是一个自然数n。

印记
打印问题的答案。
 

 

例子
<头> <正文>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# 输入 输出
1 2 1