Đếm Số Trong Đoạn

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
algorit , bin9638
Dạng bài
Điểm: 2300 (p) Thời gian: 3.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

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.

bin9638 cũng là \(1\) người crush Nezuko lâu năm. Bây giờ bin9638 đ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ờ bin9638 đ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 bin9638 nhé.

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


  • 14
    BETTER    9:29 p.m. 3 Tháng 1, 2021

    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Á=))))


    • -2
      Toilaaibanbietko7A4    10:01 a.m. 6 Tháng 1, 2021

      Ả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 à???


      • -1
        BETTER    8:17 p.m. 21 Tháng 2, 2021

        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:)


        • -2
          Toilaaibanbietko7A4    8:36 a.m. 22 Tháng 2, 2021

          Ừ, lớp 8 (đặt là 7A4 vì lúc mới lập còn là kì nghỉ hè lớp 7)


          • 0
            hoangphucnguyen    8:55 p.m. 3 Tháng 9, 2024

            Đã là 4 năm kể từ khi bạn comment rồi, giờ chắc cũng ko còn là cậu bé lớp 7, lớp 8 ngày nào nữa mà giờ đã là một thk thanh niên lớp 10 rồi, chúc bạn may mắn, nếu bạn thấy tin nhắn này, hãy để cho tớ 1 lời nhắn cuối cùng. Bye


            • 0
              algorit    6:21 p.m. 12 Tháng 10, 2024

              4 năm trôi nhanh quá :"((
              Nhớ hồi xưa vẫn cày cày ra đề cho LQDOJ Contest


            • -1
              nguyenthanhtai24122013    10:45 a.m. 11 Tháng 10, 2024

              i make you more skibidi toilet man (stupid)


            • 0
              BETTER    8:36 p.m. 22 Tháng 2, 2021

              :VVVV


          • -1
            BETTER    8:15 p.m. 8 Tháng 1, 2021

            :V


            • -5
              HH_Hoang    9:40 p.m. 6 Tháng 1, 2021

              Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


              • -5
                Toilaaibanbietko7A4    9:44 a.m. 7 Tháng 1, 2021

                Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

            11 bình luận nữa