[Ninh Bình - TS10 - 2024] Bài 3: Số đặc biệt
Xem dạng PDF
Gửi bài giải
Điểm:
8,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Người đăng:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch
Một số nguyên dương được gọi là số đặc biệt nếu nó có đúng ~3~ ước nguyên dương đôi một khác nhau.
Yêu cầu: Cho ~M~ cặp số nguyên dương ~(a; b)~, hãy đếm số lượng số đặc biệt ~x~ thoả mãn ~a \leq x \leq b~.
INPUT
- Dòng đầu là số nguyên dương ~M~ ~(1 \leq M \leq 10^5)~;
- ~M~ dòng tiếp theo mỗi dòng chứa hai số nguyên dương ~a, b~ cách nhau bởi một khoảng trắng ~(1 \leq a \leq b \leq 10^6)~.
OUTPUT
- Ghi ra kết quả gồm ~M~ dòng, mỗi dòng là kết quả tương ứng tìm được.
SAMPLE INPUT
2
1 10
1 100
SAMPLE OUTPUT 1
2
4
SUBTASKS
- Có ~20\%~ số điểm ứng với ~(1 \leq M \leq 10^2; 1 \leq b \leq 10^3)~;
- Có ~30\%~ số điểm ứng với ~(1 \leq M \leq 10^3; 1 \leq b \leq 10^5)~;
- ~50\%~ số điểm còn lại không có giới hạn gì thêm.
Bình luận
include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
int main() { ios::syncwithstdio(false); cin.tie(nullptr); vector<bool> isPrime(MAXN + 1, true); isPrime[0] = isPrime[1] = false; for (int i = 2; 1LL * i * i <= MAXN; i++) { if (isPrime[i]) { for (int j = i * i; j <= MAXN; j += i) { isPrime[j] = false; } } } vector<int> prefix(MAXN + 1, 0); for (int p = 2; p * p <= MAXN; p++) { if (isPrime[p]) { prefix[p * p] = 1; } } for (int i = 1; i <= MAXN; i++) { prefix[i] += prefix[i - 1]; } int M; cin >> M; while (M--) { int a, b; cin >> a >> b; cout << prefix[b] - prefix[a - 1] << '\n'; }
}