Nguyên tố cùng nhau
Xem dạng PDF
Gửi bài giải
Điểm:
10,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho số nguyên dương N. Hãy đếm số lượng số nguyên dương i không vượt quá N sao cho ~\gcd(i,N)=1~.
Trong đó, ~\gcd(a,b)~ là ước chung lớn nhất của hai số nguyên dương a và b.
Input
Dòng đầu tiên chứa số nguyên
Tlà số lượng bộ test (~1 \le T \le 10~).Tdòng tiếp theo, mỗi dòng chứa một số nguyênN(~1 \le N \le 10^9~).
Output
- Gồm
Tdòng, mỗi dòng chứa kết quả tương ứng với một bộ test.
Ví dụ
Sample Input
5
100
200
155
210
985
Sample Output
40
80
48
48
784
Phân chia điểm
Subtask 1 (50% số điểm): ~1 \le N \le 10^5~.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Bình luận