Hướng dẫn giải của [VT Thiếu nhi] BÀI 06: EULER
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 số cặp số nguyên tố ~x \le y~ với ~x + y = N~ (bài toán kiểu Goldbach).
Sub 1: Vét cạn — ~O(N \sqrt{N})~, dùng khi ~N \le 1000~
Thử ~x~ từ 2 đến ~N/2~, kiểm tra ~x~ và ~N-x~ nguyên tố bằng thử chia. Chạy riêng sub này: đúng 20/20 test.
Sub 2: Sàng nguyên tố — ~O(N \log \log N)~
Sàng các số nguyên tố đến ~N~ một lần, rồi đếm ~x~ với ~x~ và ~N-x~ đều nguyên tố. Chạy riêng sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Chương trình đọc ~N~; nếu ~N \le 1000~ gọi sub1, còn lại gọi sub2.
Số test: 20 (chương trình đầy đủ đúng 20/20).
#include <bits/stdc++.h>
using namespace std;
long long N;
// Kiem tra v co phai so nguyen to khong (thu chia den sqrt(v))
bool isPrimeTD(long long v) {
if (v < 2) return false;
for (long long d = 2; d * d <= v; d++)
if (v % d == 0) return false;
return true;
}
// Sub 1: vet can. Thu tung x tu 2 den N/2 (de x <= y), kiem tra x va N-x deu la so nguyen to
// bang thu chia. Dung khi N <= 1000
void sub1() {
long long cnt = 0;
for (long long x = 2; 2 * x <= N; x++)
if (isPrimeTD(x) && isPrimeTD(N - x)) cnt++;
cout << cnt << "\n";
}
// Sub 2: day du. Sang nguyen to den N mot lan, sau do dem cac x (x <= N/2) ma x va N-x deu nguyen to.
// O(N log log N). Dung cho N lon.
bool comp[100005];
void sub2() {
comp[0] = comp[1] = true;
for (long long i = 2; i * i <= N; i++)
if (!comp[i])
for (long long j = i * i; j <= N; j += i) comp[j] = true;
long long cnt = 0;
for (long long x = 2; 2 * x <= N; x++)
if (!comp[x] && !comp[N - x]) cnt++;
cout << cnt << "\n";
}
int main() {
freopen("EULER.INP", "r", stdin);
freopen("EULER.OUT", "w", stdout);
cin >> N;
if (N <= 1000) sub1();
else sub2();
return 0;
}
Bình luận