Mã bài:
sumdiv
Điểm:
1,5 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Dữ liệu vào:
sumdiv.inp
Dữ liệu ra:
sum.out
Tác giả:
Dạng bài
Mỗi bài tập chỉ được phép nộp ~2~ lần trong suốt contest.
Với mỗi số nguyên ~n~, ta gọi ~G_n~ là tổng tất cả các ước nguyên tố của ~n~. Bạn được cho ~T~ cặp số ~l~ và ~r~, nhiệm vụ của bạn là hãy tính tổng ~G_i~ với ~l \le i \le r~.
Dữ liệu
Nhập từ file sumdiv.inp
:
- Dòng đầu tiên là số nguyên ~T~ ~(1 \le T \le 10^6)~.
- ~T~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~l~ và ~r~ ~(1 \le l \le r \le 10^6)~, cách nhau bởi dấu cách.
Kết quả
- Xuất ra file
sum.out
~T~ số nguyên là kết quả cần tìm sau khi chia lấy phần dư cho ~1000000007~, mỗi số nằm trên một dòng.
Giới hạn
- Subtask ~1~ ~(20\%)~: ~T \le 10~ và ~r \le 1000~.
- Subtask ~2~ ~(50\%)~: ~T \le 100~ và ~r \le 10^4~.
- Subtask ~3~ ~(30\%)~: không có giới hạn nào thêm.
Ví dụ
Dữ liệu
2
1 2
1 3
Kết quả
2
5
Giải thích
- Ở testcase đầu tiên, ~G_1 = 0, G_2 = 2, G_1 + G_2 = 0 + 2 = 2~
Bình luận