Module: 数論におけるオイラー関数とその他の問題


Problem

1 /9


オイラー関数

Theory Click to read/hide

オイラー関数

この理論はこちらで読むことができます。

Problem

自然数 \(n <= 10^9,\) を指定して、\ より小さい自然数の数を決定します。 (n\ )\(n\) と互いに素です。この数は \( f(n) \) で表され、オイラーのファイ関数と呼ばれます。アルゴリズムの複雑さは\( 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