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
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)
-
2
algorit
10:31 a.m. 29 Tháng 7, 2020
-
1
hhoangcpascal
6:52 a.m. 29 Tháng 7, 2020
4 bình luận nữa😆
:V