Phép chia hết

View as PDF
Submit solution
Points: 0.14 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem source:
quocquan
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • 1
    Thinh_CNTT4_K61  commented on Jan. 26, 2022, 1:23 p.m.

    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 ạ


    • 11
      PPAP_1264589  commented on Jan. 29, 2022, 1:47 p.m.

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