Độ khó: Khá (3/4 điểm)

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Thầy Sơn có ~N~ viên kẹo và muốn làm một thí nghiệm nhỏ với lớp mình. Lần lượt với ~k = 1, 2, \dots, M~, thầy chia đều ~N~ viên kẹo cho ~k~ bạn: mỗi bạn nhận số kẹo như nhau và nhiều nhất có thể, phần kẹo còn dư (đúng bằng ~N \bmod k~) thầy giữ lại cho mình. Kẹo được gom lại trước mỗi lần chia.

Hãy tính tổng số kẹo thầy Sơn giữ lại sau ~M~ lần chia:

~S = \sum_{k=1}^{M} (N \bmod k)~

Vì ~S~ có thể rất lớn, hãy in ra ~S~ chia lấy dư cho ~10^9 + 7~.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên ~N~ và ~M~ ~(1 \le N, M \le 10^{12})~.

Kết quả

Một số nguyên duy nhất là ~S \bmod (10^9 + 7)~.

Giới hạn (Subtask)

• Subtask 1 (~30\%~ số điểm): ~N, M \le 10^6~.
• Subtask 2 (~40\%~ số điểm): ~M \le N~.
• Subtask 3 (~30\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 3 giây.

Sample Input 1

10 15

Sample Output 1

63

Sample Input 2

7 3

Sample Output 2

2

Giải thích

• Ví dụ 1: với ~k = 1, \dots, 10~ phần dư lần lượt là ~0, 0, 1, 2, 0, 4, 3, 2, 1, 0~ (tổng ~13~); với ~k = 11, \dots, 15~ không chia được viên nào cho mỗi bạn nên dư cả ~10~ viên, cộng thêm ~5 \times 10 = 50~. Tổng ~63~.
• Ví dụ 2: ~7 \bmod 1 + 7 \bmod 2 + 7 \bmod 3 = 0 + 1 + 1 = 2~.

Nguồn: Đề tự luyện HSG Tin học lớp 12 (đề tự soạn).