SH10 - TỔNG SỐ LƯỢNG ƯỚC
Xem dạng PDF
Gửi bài giải
Điểm:
3,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
Với mỗi số nguyên dương ~i~, gọi ~d(i)~ là số lượng ước của ~i~. Cho số nguyên dương ~n~, hãy tính
~T(n) = d(1) + d(2) + d(3) + \dots + d(n)~
Input:
Một dòng duy nhất chứa số nguyên ~n~.
Output:
Một số nguyên duy nhất là giá trị ~T(n)~.
Ràng buộc:
~1 \le n \le 10^{12}~.
- Subtask 1 (25% số điểm): ~n \le 10^4~.
- Subtask 2 (35% số điểm): ~n \le 10^7~.
- Subtask 3 (40% số điểm): ~n \le 10^{12}~.
Ví dụ:
Input
6
Output
14
Input
100
Output
482
Giải thích ví dụ 1: ~d(1)=1~, ~d(2)=2~, ~d(3)=2~, ~d(4)=3~, ~d(5)=2~, ~d(6)=4~. Tổng bằng ~14~.
Gợi ý: hãy đếm xem mỗi số ~i~ là ước của bao nhiêu số không vượt quá ~n~.
Bình luận