Module: Hàm Euler và các vấn đề khác trong lý thuyết số


Problem

1 /9


hàm Euler

Theory Click to read/hide

Hàm Euler

Bạn có thể đọc lý thuyết này tại đây.

Problem

Cho một số tự nhiên \(n  <= 10^9,\) xác định số các số tự nhiên nhỏ hơn \ (n\ ) và đồng nguyên tố với \(n\). Con số này được ký hiệu là \( f(n) \) và được gọi là hàm phi của Euler. Độ phức tạp của thuật toán phải là \( O(\sqrt{n})\) .

Đầu vào
Đầu vào là một số tự nhiên n.

Dấu ấn
In câu trả lời cho vấn đề.
 

 

Ví dụ
<đầu>

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!

# Đầu vào Đầu ra
1 2 1