Hướng dẫn giải của Phân tích số (đề KS ĐH 2024)
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
Đếm bộ ba số nguyên tố đôi một khác nhau ~a < b < c~ có tổng bằng ~n~. Các bộ được tính không kể thứ tự.
Sub 1: Vét cạn ba vòng lặp — ~O(P^3)~ với ~P~ là số nguyên tố không vượt quá ~n~, dùng khi ~n \le 215~
Lập danh sách số nguyên tố, rồi thử mọi bộ ba ~i < j < k~.
Nếu chỉ nộp sub này: đúng 16/19 test.
Sub 2: Hai vòng lặp và sàng — ~O(P^2)~
Chọn ~a < b~ nguyên tố, với ~2b < n - a~ (để ~c > b~), kiểm tra ~c = n - a - b~ có là nguyên tố bằng bảng sàng. Dừng vòng lặp khi vượt điều kiện.
Nếu chỉ nộp sub này: đúng 19/19 test.
Chương trình hoàn chỉnh
Dữ liệu ~n \le 215~ dùng sub 1, còn lại dùng sub 2.
#include <bits/stdc++.h>
using namespace std;
long long n;
vector<bool> comp; // sang nguyen to den n
bool isPrime(long long x) {
if (x < 2) return false;
return !comp[x];
}
// Sub 1: vet can, duyet 3 so nguyen to a < b < c voi a + b + c = n. O(P^3) voi P la so nguyen to <= n.
// Dung khi n <= 215.
void sub1() {
vector<long long> pr;
for (long long i = 2; i <= n; i++) if (isPrime(i)) pr.push_back(i);
long long cnt = 0;
for (size_t i = 0; i < pr.size(); i++)
for (size_t j = i + 1; j < pr.size(); j++)
for (size_t k = j + 1; k < pr.size(); k++)
if (pr[i] + pr[j] + pr[k] == n) cnt++;
cout << cnt << "\n";
}
// Sub 2: chon a < b (ca hai la nguyen to), c = n - a - b phai la nguyen to va c > b.
// Dieu kien c > b <=> 2b < n - a nen dung break khi vuot. O(P^2) voi sang nguyen to.
void sub2() {
vector<long long> pr;
for (long long i = 2; i <= n; i++) if (isPrime(i)) pr.push_back(i);
long long cnt = 0;
for (size_t i = 0; i < pr.size(); i++) {
long long a = pr[i];
for (size_t j = i + 1; j < pr.size(); j++) {
long long b = pr[j];
if (a + 2 * b >= n) break; // khi do c = n-a-b <= b
long long c = n - a - b;
if (isPrime(c)) cnt++;
}
}
cout << cnt << "\n";
}
int main() {
cin >> n;
comp.assign(n + 2, false);
comp[0] = comp[1] = true;
for (long long i = 2; i * i <= n + 1; i++)
if (!comp[i])
for (long long j = i * i; j <= n + 1; j += i) comp[j] = true;
if (n <= 215) sub1();
else sub2();
return 0;
}
Bình luận