Phân số tối giản (TS10 LQĐ, Đà Nẵng 2019)

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Thời gian:

Python 3 3.0s

Tác giả:

Small

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1300 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một phân số được gọi là phân số tối giản nếu ước chung lớn nhất của tử số và mẫu số bằng 1.

Yêu cầu: Cho trước một số nguyên dương \(N\). Hãy đếm xem có bao nhiêu phân số dương bé hơn 1, có mẫu là \(N\) và là phân số tối giản.

Input

Chứa một số nguyên dương \(N\) (\(N ≤ 10^{16}\)).

Ouput

Ghi ra số nguyên \(M\) là số lượng phân số theo yêu cầu trên

Example

Test 1

Input

Output

Note

Có 6 phân số dương bé hơn 1 có mẫu bằng 9 và là phân số tối giản là \(\frac{1}{9};\frac{2}{9};\frac{4}{9};\frac{5}{9};\frac{7}{9};\frac{8}{9}\)

Nguồn: TS10LQD 2019

Bình luận (6)

Tải bình luận...