Hướng dẫn giải của [KS cụm 2 QL] Câu 1: Đếm số
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho ~L~ và ~k~, cần tìm số không nguyên tố thứ ~k~ và số nguyên tố thứ ~k~ tính từ ~L~ (tính cả ~L~ nếu thỏa mãn). Số 1 không phải số nguyên tố.
Sub 1: Thử từng số — ~O(x \sqrt{x})~ với ~x~ là đáp án, dùng khi ~L \le 100~ và ~k \le 100~
Duyệt ~x~ từ ~L~ trở đi, mỗi số kiểm tra nguyên tố bằng thử chia đến căn bậc hai. Đếm số nguyên tố và số không nguyên tố, khi đủ ~k~ thì lấy kết quả. Đủ nhanh vì đáp án nhỏ.
Nếu chỉ nộp sub này: đúng 15/20 test.
Sub 2: Sàng với giới hạn tăng dần — ~O(M \log \log M)~ với ~M~ là giới hạn sàng, dùng khi mọi trường hợp còn lại
Chọn giới hạn ~M~ khoảng ~2(L+k)~ rồi sàng số nguyên tố đến ~M~. Đếm từ ~L~ đến ~M~: nếu đủ ~k~ số nguyên tố và ~k~ số không nguyên tố thì dừng; nếu chưa đủ thì nhân đôi ~M~ và làm lại. Với ~L = 1~ và ~k~ lớn, đáp án là số nguyên tố thứ ~k~ khoảng ~10^7~ nên vẫn chạy kịp.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Đề có các subtask theo ~L~ và ~k~. Sub 1 dùng cho ~L \le 100~ và ~k \le 100~, sub 2 dùng cho phần còn lại.
Chương trình đọc ~L, k~. Nếu ~L \le 100~ và ~k \le 100~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long L, k;
bool laNguyenTo(long long x) {
if (x < 2) return false;
for (long long d = 2; d * d <= x; d++)
if (x % d == 0) return false;
return true;
}
// Sub 1: L <= 100 va k <= 100. Duyet x tu L, kiem tra nguyen to bang thu chia, dem.
void sub1() {
long long cntP = 0, cntN = 0, resP = 0, resN = 0;
for (long long x = L; cntP < k || cntN < k; x++) {
if (laNguyenTo(x)) {
if (++cntP == k) resP = x;
} else {
if (++cntN == k) resN = x;
}
}
cout << resN << " " << resP << "\n";
}
// Sub 2: sang so nguyen to den gioi han lim, dem tu L. Neu chua du thi nhan doi lim.
void sub2() {
long long lim = 2 * (L + k) + 1000;
while (true) {
vector<bool> comp(lim + 1, false);
comp[0] = comp[1] = true;
for (long long i = 2; i * i <= lim; i++)
if (!comp[i])
for (long long j = i * i; j <= lim; j += i) comp[j] = true;
long long cntP = 0, cntN = 0, resP = 0, resN = 0;
for (long long x = L; x <= lim; x++) {
if (!comp[x]) {
if (++cntP == k) resP = x;
} else {
if (++cntN == k) resN = x;
}
}
if (cntP >= k && cntN >= k) {
cout << resN << " " << resP << "\n";
return;
}
lim *= 2;
}
}
int main() {
freopen("CAU1.inp", "r", stdin);
freopen("CAU1.out", "w", stdout);
cin >> L >> k;
if (L <= 100 && k <= 100) sub1();
else sub2();
return 0;
}
Bình luận