Đếm số (THT B Vòng Sơ loại Toàn quốc 2026 - Lần 1)
Xem PDF
Điểm:
1900 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho hai số nguyên dương \(A\) và \(B\) (\(A \le B\)).
Một số nguyên \(X\) được gọi là thỏa mãn nếu đồng thời thỏa cả ba điều kiện sau:
- \(A \le X \le B\);
- Tổng các chữ số của \(X\) là một số nguyên tố;
- Số lượng ước số dương của \(X\) là một số chẵn.
Yêu cầu
Cho \(T\) truy vấn. Mỗi truy vấn gồm hai số \(A_i, B_i\). Với mỗi truy vấn, hãy đếm số lượng số \(X\) thỏa mãn trong đoạn \([A_i, B_i]\).
Input
- Dòng đầu tiên chứa số nguyên dương \(T\).
- \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(A_i, B_i\) (\(A_i \le B_i\)).
Output
- Gồm \(T\) dòng, mỗi dòng in ra một số nguyên là kết quả của truy vấn tương ứng.
Example
Test 1
Input
2
1 9
10 15Output
4
3Note
- Với đoạn \([1, 9]\): Các số thỏa mãn là: \(2, 3, 5, 7\) (tổng chữ số là số nguyên tố, và số ước của mỗi số là chẵn).
- Với đoạn \([10, 15]\):
- \(10\): tổng chữ số \(= 1\) (không phải số nguyên tố) \(\rightarrow\) loại.
- \(11\): tổng \(= 2\) (nguyên tố), số ước \(= 2\) (chẵn) \(\rightarrow\) thỏa mãn.
- \(12\): tổng \(= 3\) (nguyên tố), số ước \(= 6\) (chẵn) \(\rightarrow\) thỏa mãn.
- \(13\): tổng \(= 4\) (không nguyên tố) \(\rightarrow\) loại.
- \(14\): tổng \(= 5\) (nguyên tố), số ước \(= 4\) (chẵn) \(\rightarrow\) thỏa mãn.
- \(15\): tổng \(= 6\) (không nguyên tố) \(\rightarrow\) loại.
Các số thỏa mãn là: \(11, 12, 14 \rightarrow\) có \(3\) số.
Scoring
- Subtask \(1\) (\(40\%\) số điểm): \(T = 1; 1 \le A_i \le B_i \le 10^3\).
- Subtask \(2\) (\(40\%\) số điểm): \(T \le 10^5; 1 \le A_i \le B_i \le 10^7\).
- Subtask \(3\) (\(20\%\) số điểm): \(T \le 10^5; 1 \le A_i \le B_i \le 10^{14}\).
Kỳ thi:
- THT B Vòng Sơ loại Toàn quốc 2026 - Lần 1 (29 Tháng ba, 2026)
Bình luận