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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.