Phân số tối giản

View as PDF

Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 64M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

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.

Dữ liệu

  • Chứa một số nguyên dương N (N1016).

Kết quả

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

Sample Input

Copy
9

Sample Output

Copy
6

Giải thích: 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à 19;29;49;59;79;89



Comments

Please read the guidelines before commenting.


There are no comments at the moment.