Nezuko là \(1\) cô bé xinh đẹp, dễ thương, là em gái quốc dân, crush trong mơ của bao thằng wibu. Hôm nay Nezuko đã khám phá ra số “Wibu”. Số “Wibu” là \(1\) số tự nhiên mà tổng các chữ số nguyên tố cùng nhau với tổng \(wibu\) của các chữ số với \(wibu(i)=\)\(1^2+2^2+…+i^2\) \((0 \leq i \leq 9)\).
Ví dụ số \(20\), có tổng các chữ số là \(2+0=2\) và tổng \(wibu=wibu(2)\)\(+wibu(0)=5\) nguyên tố cùng nhau nên là số “Wibu”. Còn số \(33\) có tổng các chữ số là \(3+3=6\) và tổng \(wibu=wibu(3)\)\(+wibu(3)=28\) không nguyên tố cùng nhau nên không phải.
\(1\) người crush Nezuko lâu năm. Bây giờ đang muốn tính tổng các số “Wibu” trong đoạn từ \(l\) đến \(r\) \((l,r \leq 10^{18})\) để lấy le với Nezuko, nhưng khổ nỗi bây giờ đang mãi hóng movie mới của Kimetsu No Yaiba nên không có thời gian tính toán. Các bạn hãy giúp nhé.
cũng làVì kết quả có thể rất lớn nên các bạn hãy in kết quả chia lấy dư cho \(10^9+7\).
Yêu cầu:
- Tính tổng các số “Wibu” trong đoạn \([l,r]\)
Input
- Dòng đầu tiên là số truy vấn \(q\) \((q ≤ 10^5)\).
- \(q\) dòng tiếp theo mỗi dòng là \(2\) số \(l,r\).
Output
- Gồm \(q\) dòng, mỗi dòng là kết quả cho truy vấn tương ứng.
Scoring
-
Subtask \(1\) (\(40\%\) số điểm): \(l,r \leq 10^6\), \(q ≤ 10\).
-
Subtask \(2\) (\(60\%\) số điểm): không có ràng buộc gì thêm.
Example
Test 1
Input
2
19 20
1 100
Output
20
3268
Bình luận
Nezuko là 1 cô bé xinh đẹp, dễ thương, là em gái quốc dân, crush trong mơ của bao thằng wibu. NHÁ=))))
Ảo tưởng sức mạnh nhá ae. Đập con nhỏ đó đi cho ròi, để nó sống làm giề? Để xuất hiện trong bài tập à???
Trả lời tên trên trang của og thì og là Trần Hoàng Nguyên :))))))))))
Lớp mấy thì ko bt:)
Ừ, lớp 8 (đặt là 7A4 vì lúc mới lập còn là kì nghỉ hè lớp 7)
:VVVV
:V
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.