Hướng dẫn giải của [200 đề thầy Đức] Bài 91: Tìm số
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
Với mỗi bộ A, B, cần tìm C nhỏ nhất để A + B + C là số nguyên tố. Tổng A + B không quá 20000 nên có thể làm theo cách thử trực tiếp hoặc dùng bảng số nguyên tố.
Sub 1: Thử từng C và kiểm tra nguyên tố — ~O(T · C · √n)~
Với C = 1, 2, 3, ..., kiểm tra A + B + C bằng cách thử chia đến căn bậc hai. Dừng khi gặp số nguyên tố. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
// Kiểm tra số nguyên tố bằng cách thử chia (vét cạn)
bool laNguyenTo(long long n) {
if (n < 2) return false;
for (long long d = 2; d * d <= n; d++)
if (n % d == 0) return false;
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
long long a, b;
cin >> a >> b;
// Thử C = 1, 2, 3, ... cho đến khi A + B + C là số nguyên tố
for (long long c = 1;; c++) {
if (laNguyenTo(a + b + c)) {
cout << c << "\n";
break;
}
}
}
return 0;
}
Sub 2: Sàng số nguyên tố — ~O(N log log N + T · gap)~
Sàng số nguyên tố đến 40000 một lần. Với mỗi bộ, tìm số nguyên tố p nhỏ nhất lớn hơn A + B; đáp án là p - (A + B). Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Sàng số nguyên tố đến 40000 (A + B <= 20000, khoảng cách giữa hai số nguyên tố liên tiếp rất nhỏ)
const int MAXN = 40000;
vector<bool> laNT(MAXN + 1, true);
laNT[0] = laNT[1] = false;
for (int i = 2; i * i <= MAXN; i++)
if (laNT[i])
for (int j = i * i; j <= MAXN; j += i) laNT[j] = false;
int T;
cin >> T;
while (T--) {
int a, b;
cin >> a >> b;
int s = a + b;
// C nhỏ nhất sao cho s + C là số nguyên tố = (số nguyên tố nhỏ nhất > s) - s
int p = s + 1;
while (!laNT[p]) p++;
cout << p - s << "\n";
}
return 0;
}
Bình luận