Bài toán Số học

Xem PDF
Tác giả:
hhoangcpascal
Dạng bài
Điểm: 1700 (p) Thời gian: 0.4s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Một ngày, khi học sinh lớp \(1\) đang học về số học, giáo sư Wu Zi Mu đã ra bài tập như sau:

“Định nghĩa \(F(N)\) là số ước nguyên dương của \(N\). Ví dụ: \(F(12)=6,F(5)=2\).

Cho \(Q\) truy vấn, mỗi truy vấn chứa hai số \(A,B\). Nhiệm vụ là đếm tất cả số \(X\) nằm trong khoảng [A,B] mà \(F(X)\) là số nguyên tố lớn hơn \(2\).”

Học sinh lớp \(1\) đang cố tìm cách để giải bài này, nhưng không tìm ra được. Các bạn hãy giúp cho các học sinh đó nhé.

Input

  • Gồm \(Q+1\) dòng:
  • Dòng đầu tiên gồm số \(Q\) là số truy vấn.
  • \(Q\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(A,B\).

Output

  • Gồm \(Q\) dòng là kết quả của \(Q\) truy vấn .

Constraints

  • \(1 \leq A,B \leq 10^{12}\)
  • \(1 \leq Q \leq 10^{5}\)

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(1 \leq A,B \leq 10^{3}, Q \leq 10^3\).
  • Subtask \(2\) (\(30\%\) số điểm): \(1 \leq A,B \leq 10^{6}, Q \leq 10^5\).
  • Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
2
3 25
1 100
Output 
4
7

Bình luận


  • 6
    longkold00    8:58 a.m. 4 Tháng 10, 2021 ← chỉnh sửa 4

    Mình có 1 số ý tưởng của bài này và muốn chia sẻ cho mọi người cùng thảo luận như sau:

    1. Ta nhận thấy số truy vấn lớn + giới hạn A,B lớn và quỹ thời gian giới hạn là 0.4s, yêu cầu ta phải giải các truy vấn trong ít nhất là O(1).

    2. Bài toán đề cập tới số ước nguyên dương, nếu dùng sàng bình thường thì với bộ dữ liệu 10^12 chắc chắn sẽ tle, nên chắc chắn sẽ có điều gì đó đặc biệt.

    3. Đề bài yêu cầu số lượng ước phải là 1 số nt lớn hơn 2??? tức có nghĩ là số ước phải là 1 số LẺ + Nguyên tố. mà 1 số như vậy thì sẽ phải được tạo nên từ hàm mũ của 1 số nguyên tố với số mũ là 1 số nguyên tố trừ đi 1 (theo công thức tính số ước)

    4. Từ ý 3, chúng ta chỉ cần sàng nguyên tố đến các số <=10^6 do số phải đc tạo ít nhất từ mũ 3-1=2 :V

    Bây giờ chúng ta sẽ xử lý các truy vấn như sau:

    1. tạo 1 mảng chứa 11 số nguyên số đầu tiên (không kể số 2), và giảm các số đó đi 1 đơn vị x[11]={2,4,6,10,12,16,18,22,28,30,36}

    2. ta tạo 1 hàm duyệt để nạp các số h thỏa mãn đề bài vào 1 mảng a[] như sau:

    nếu h>=1000 ta nạp h^2 vào a[]

    nếu h<1000 ta dùng vòng for duyệt từng phần tử trong mảng x[],nếu h^x[i]<=lim (ở đây là 10^12) ta nạp vào a[],ngược lại ta dừng vòng lặp.

    1. sử dụng sàng và hàm duyệt để hoàn thành mảng a[] chứa các số thỏa mãn, sau đó sort chúng lại

    2. với mỗi truy vấn ta sử dụng chặt nhị phân để tìm chỉ số của số >=A và >B, sau đó tính số số thỏa mãn là đc.


    • -1
      vnedu    1:51 p.m. 23 Tháng 7, 2023 ← đã chỉnh sửa

      .


      • 1
        VoBaThongL921    10:45 a.m. 4 Tháng 10, 2021

        Anh muốn cải tiến sàng số nguyên tố thì có thể xem ở đây ạ:> https://hackmd.io/4N-JNh6GToSt_wVRhREKqg?view


        • 2
          longkold00    10:56 a.m. 4 Tháng 10, 2021

          A vừa ac rùi ó :v chặt nhị phân ko bị tle đou. Cảm ơn em đã chia sẻ.


      • 3
        lethienquan28052006    9:55 a.m. 4 Tháng 10, 2021

        bạn thử cho vào mảng tất cả các số đó, sau đó chặt nhị phân :v,


        • 2
          VoBaThongL921    10:34 a.m. 4 Tháng 10, 2021

          ủa chặt nhị phân có tle không ạ :v


          • 1
            longkold00    10:34 a.m. 9 Tháng 10, 2021

            Đổi avatar rùi hả e :v


            • 0
              VoBaThongL921    10:37 a.m. 9 Tháng 10, 2021

              Dạ:) Do có bạn hỏi cách đổi nên em đổi lại


          • 2
            stormgamming    10:20 a.m. 4 Tháng 10, 2021 ← đã chỉnh sửa

            .


            • 2
              longkold00    9:58 a.m. 4 Tháng 10, 2021

              cảm ơn bạn nhé, vừa cũng mới có 1 bạn bên vnoi chỉ mình chặt nhị phân :V

          4 bình luận nữa