Phép chia hết

Xem dạng PDF

Gửi bài giải


Điểm: 0,14 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Nguồn bài:
quocquan
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho ~2~ số ~A~ và ~B~. Tính xem có bao nhiêu số trong ~[A~, ~B]~ chỉ chia hết cho đúng ~2~ trong ~3~ số ~4~, ~6~ và ~15~.

Input

  • Dòng đầu là số test ~T~ ~(T \le 10^{5})~
  • ~T~ dòng tiếp theo mỗi dòng là ~2~ số nguyên ~A~, ~B~. ~(0 < A \le B \le 10^{18})~

Output

  • ~T~ dòng, mỗi dòng là một kết quả của bài toán.

Sample Input

2
1 20
2 30

Sample Output

1
3

Bình luận

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



  • 1
    Thinh_CNTT4_K61  đã bình luận lúc 26, Tháng 1, 2022, 13:23

    Ai có thể giải thích giúp em code trong phần lời giải được không. Em cảm ơn ạ


    • 14
      PPAP_1264589  đã bình luận lúc 29, Tháng 1, 2022, 13:47

      COMMENT NÀY SPOIL THUẬT !

      Biểu diễn tập hợp các số nhỏ hơn hoặc bằng ~n~ chia hết cho ~x,y,z~ bằng biểu đồ Venn

      Gọi ~G(x,y,n) = n/LCM(x,y)~ là số số chia hết cho ~(x,y)~ trong khoảng ~[1, n]~
      Gọi ~P(x,y,z,n) = n/LCM(x,y,z)~ là số số chia hết cho ~(x,y,z)~ trong khoảng ~[1, n]~
      Gọi ~F(n)~ là số số chia hết cho 2 trong 3 số ~(x,y,z)~ trong khoảng ~[1, n]~

      ~F(n) = G(x,y,n) + G(y,z,n) + G(z,x,n) - P(x,y,z,n)~ Minh họa

      Đáp án bài toán trong khoảng ~[A,B]~ là ~F(B) - F(A-1)~