Tổng số nguyên tố cùng nhau
Xem dưới dạng PDF
Gửi bài giải
Điểm:
15
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
đầu vào:
stdin
Đầu ra:
stdout
Tác giả:
Kiểu bài tập
Cho \(N\). Tính tổng các số \(x\) trong \([1, N]\) mà \(\gcd(x, N) = 1\).
Định dạng đầu vào
- Một dòng chứa \(N\) (\(1 \le N \le 10^{12}\)).
Định dạng đầu ra
- Một số nguyên là tổng modulo \(10^9+7\).
Ví dụ
Input:
6Output:
12Giải thích: Các số \(\gcd(x,6)=1\): 1,5. Tổng = 6.
Ràng buộc
- 100% số điểm: \(N \le 10^{12}\).
Nhận xét