Bài toán Số học
Xem PDF
Đ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
admin cho time limit chặt quá.
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:
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).
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.
Đề 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)
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:
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}
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:
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
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.
Em xin idea this problem
mấy em học sinh lớp 1 bài này kiểu!
Bài này cá nhân mình thấy rất là hay, cảm ơn vì ý tưởng của người ra đề. Tuy nhiên đáng buồn là mặc dù chỉ nhập vào 10^5 số, mình không dùng lệnh tắt đồng bộ ios.... thì tạch time limit còn thêm vào thì AC với thời gian khá tốt (tiệm cận người ra đề), làm mình debug cả buổi tối không hiểu vì sao sai 😢 (cho tới khi tự sinh test max cho chạy thử trên máy)