Hướng dẫn giải của [KSCUM VT] CÂU 1
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Các số không nguyên tố (kể cả số 1) được liệt kê theo thứ tự tăng dần. Cần tìm số không nguyên tố thứ ~k~ tính từ ~L~ (đếm cả ~L~ nếu ~L~ không nguyên tố). Đề yêu cầu đọc file ~CAU1.INP~ và ghi ra ~CAU1.OUT~.
Sub 1: Duyệt từ L và chia thử — ~O(k \sqrt{x})~, dùng khi ~L \le 100~ và ~k \le 10^4~
Duyệt ~x~ từ ~L~ lên, kiểm tra từng số bằng chia thử và đếm số không nguyên tố. Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 2: Sàng Eratosthenes đến 2 \cdot 10^6 — ~O(M \log \log M)~
Sàng đến ~2 \cdot 10^6~ (đủ cho ~k \le 6 \cdot 10^5~), đánh dấu số không nguyên tố và duyệt từ ~L~ đến khi đếm đủ ~k~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc ~L, k~, nếu ~L \le 100~ và ~k \le 10^4~ gọi sub1, ngược lại gọi sub2. Chương trình có ~freopen~ đọc ~CAU1.INP~ và ghi ~CAU1.OUT~.
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 2000000; // gioi han sang cho sub2
bool composite[MAXV + 1]; // composite[x] = true neu x khong phai nguyen to (1 cung khong phai nguyen to)
long long L, K;
// Kiem tra nguyen to bang chia thu
bool isPrimeTD(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, k <= 10^4: duyet tu L, dem so khong nguyen to bang chia thu.
void sub1() {
long long cnt = 0;
for (long long x = L;; x++)
if (!isPrimeTD(x)) {
cnt++;
if (cnt == K) { cout << x << "\n"; return; }
}
}
// Sub 2: sang Eratosthenes den 2*10^6, duyet tu L dem so khong nguyen to.
void sub2() {
composite[0] = composite[1] = true;
for (long long i = 2; i * i <= MAXV; i++)
if (!composite[i])
for (long long j = i * i; j <= MAXV; j += i) composite[j] = true;
long long cnt = 0;
for (long long x = L; x <= MAXV; x++)
if (composite[x]) {
cnt++;
if (cnt == K) { cout << x << "\n"; return; }
}
}
int main() {
freopen("CAU1.INP", "r", stdin); // may cham doc/ghi file
freopen("CAU1.OUT", "w", stdout);
cin >> L >> K;
if (L <= 100 && K <= 10000) sub1();
else sub2();
return 0;
}
Bình luận