Hướng dẫn giải của Tổng nguyên tố (KS3)
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ỗi truy vấn cần tổng các số nguyên tố trong đoạn ~[A, B]~, với ~Q \le 10^6~ và ~B \le 10^6~. Cách hợp lý là sàng số nguyên tố một lần rồi cộng tiền tố để trả lời mỗi truy vấn trong ~O(1)~.
Sub 1: Vét cạn — ~O(Q \cdot (B - A) \sqrt{B})~, dùng khi ~Q, A, B \le 1000~
Với mỗi truy vấn, duyệt từng số trong ~[A, B]~ và kiểm tra nguyên tố bằng chia thử. Nếu chỉ nộp sub này: đúng 12/20 test (các test lớn bị quá giờ).
Sub 2: Sàng một lần, duyệt đoạn — ~O(M \log \log M + Q \cdot M)~ với ~M = \max B~, dùng khi ~Q = 1~
Sàng Eratosthenes đến ~M~, rồi cộng các số nguyên tố trong ~[A, B]~. Với nhiều truy vấn thì mỗi truy vấn vẫn duyệt cả đoạn, nên chậm. Nếu chỉ nộp sub này: đúng 13/20 test.
Sub 3: Tổng tiền tố — ~O(M \log \log M + Q)~
Sàng đến ~M~, đặt ~pre[x]~ là tổng các số nguyên tố không vượt quá ~x~. Mỗi truy vấn trả lời bằng ~pre[B] - pre[A-1]~. Tổng có thể lên khoảng ~3,7 \cdot 10^{10}~ nên dùng long long. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc hết truy vấn và tính ~M~ (là ~B~ lớn nhất). Nếu ~Q, A, B \le 1000~ gọi sub1; nếu ~Q = 1~ gọi sub2; còn lại gọi sub3.
#include <bits/stdc++.h>
using namespace std;
int Q;
vector<long long> A, B;
long long M; // B lon nhat
bool isPrime(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: vet can. Moi truy van duyet tung so trong [A,B], kiem tra nguyen to bang chia thu.
// Dung khi Q, A, B <= 1000.
void sub1() {
for (int q = 0; q < Q; q++) {
long long s = 0;
for (long long x = A[q]; x <= B[q]; x++)
if (isPrime(x)) s += x;
cout << s << "\n";
}
}
// Sub 2: sang nguyen to mot lan toi M (M la B lon nhat), moi truy van duyet doan [A,B].
// Dung khi Q = 1 (hoac it truy van). O(M log log M + tong doan).
void sub2() {
vector<bool> comp(M + 1, false);
comp[0] = comp[1] = true;
for (long long i = 2; i * i <= M; i++)
if (!comp[i])
for (long long j = i * i; j <= M; j += i) comp[j] = true;
for (int q = 0; q < Q; q++) {
long long s = 0;
for (long long x = A[q]; x <= B[q]; x++)
if (!comp[x]) s += x;
cout << s << "\n";
}
}
// Sub 3: sang nguyen to mot lan, cong don tong tien to. Moi truy van O(1).
void sub3() {
vector<bool> comp(M + 1, false);
comp[0] = comp[1] = true;
for (long long i = 2; i * i <= M; i++)
if (!comp[i])
for (long long j = i * i; j <= M; j += i) comp[j] = true;
vector<long long> pre(M + 1, 0);
for (long long x = 1; x <= M; x++)
pre[x] = pre[x - 1] + (comp[x] ? 0 : x);
for (int q = 0; q < Q; q++)
cout << pre[B[q]] - pre[A[q] - 1] << "\n";
}
int main() {
freopen("SUMPRIME.INP", "r", stdin);
freopen("SUMPRIME.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> Q;
A.resize(Q);
B.resize(Q);
M = 1;
long long mx = 1;
for (int q = 0; q < Q; q++) {
cin >> A[q] >> B[q];
M = max(M, B[q]);
mx = max(mx, max(A[q], B[q]));
}
if (Q <= 1000 && mx <= 1000) sub1();
else if (Q == 1) sub2();
else sub3();
return 0;
}
Bình luận