Hướng dẫn giải của [2627 KS1] CPNT
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 đoạn ~[A; B]~, tính tổng các số chính phương và đếm số chính phương có tổng ước là số nguyên tố. Vì ~B \le 10^6~ nên chỉ có tối đa 1000 số chính phương.
Sub 1: Vét cạn mỗi đoạn — dùng khi ~T \le 10^3~ và ~B \le 10^3~
Với mỗi đoạn, duyệt ~k~ sao cho ~k^2 \le B~, tính tổng ước của ~k^2~ bằng cách duyệt ước đến căn, kiểm tra nguyên tố bằng chia thử. Nếu chỉ nộp sub này: đúng 32/40 test.
Sub 2: Tiền xử lý tổng cộng dồn — ~O(1000 \cdot \sqrt{\sigma} + T)~
Chỉ có ~k \le 1000~, nên tính trước tổng ~k^2~ cộng dồn và số lượng ~k^2~ có tổng ước nguyên tố cộng dồn. Mỗi đoạn có ~hi = \lfloor \sqrt{B} \rfloor~ và ~lo = \lfloor \sqrt{A-1} \rfloor~, đáp án là hiệu hai mảng cộng dồn tại ~hi~ và ~lo~. Cần đọc/ghi nhanh vì ~T~ tới ~10^6~ (dùng scanf và gom kết quả vào một chuỗi); tổng dùng ~long long~. Nếu chỉ nộp sub này: đúng 40/40 test.
Chương trình hoàn chỉnh
main đọc toàn bộ các đoạn; nếu ~T \le 10^3~ và mọi ~B \le 10^3~ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int T;
vector<int> qa, qb;
string out;
// tổng ước của m bằng cách duyệt mọi ước
long long sigma(long long m) {
long long s = 0;
for (long long d = 1; d * d <= m; d++)
if (m % d == 0) { s += d; if (d != m / d) s += m / d; }
return s;
}
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;
}
void emit(long long s, long long c) {
out += to_string(s); out += ' '; out += to_string(c); out += '\n';
}
// Sub 1: với mỗi đoạn, duyệt k = 1.. và tính trực tiếp — dùng khi T nhỏ, B <= 1000
void sub1() {
for (int i = 0; i < T; i++) {
long long s = 0, c = 0;
for (long long k = 1; k * k <= qb[i]; k++) {
long long m = k * k;
if (m < qa[i]) continue;
s += m;
if (isPrime(sigma(m))) c++;
}
emit(s, c);
}
}
// Sub 2: tiền xử lý tổng cộng dồn theo k (k <= 1000), mỗi đoạn trả lời O(1)
void sub2() {
const int K = 1000;
vector<long long> ps(K + 1, 0), pc(K + 1, 0);
for (int k = 1; k <= K; k++) {
ps[k] = ps[k - 1] + 1LL * k * k;
pc[k] = pc[k - 1] + (isPrime(sigma(1LL * k * k)) ? 1 : 0);
}
for (int i = 0; i < T; i++) {
int hi = (int)floor(sqrt((double)qb[i]));
while (1LL * (hi + 1) * (hi + 1) <= qb[i]) hi++;
while (1LL * hi * hi > qb[i]) hi--;
int lo = (int)floor(sqrt((double)(qa[i] - 1)));
while (1LL * (lo + 1) * (lo + 1) <= qa[i] - 1) lo++;
while (1LL * lo * lo > qa[i] - 1) lo--;
emit(ps[hi] - ps[lo], pc[hi] - pc[lo]);
}
}
int main() {
freopen("CPNT.INP", "r", stdin);
freopen("CPNT.OUT", "w", stdout);
scanf("%d", &T);
qa.resize(T); qb.resize(T);
int mx = 0;
for (int i = 0; i < T; i++) { scanf("%d %d", &qa[i], &qb[i]); mx = max(mx, qb[i]); }
if (T <= 1000 && mx <= 1000) sub1();
else sub2();
fputs(out.c_str(), stdout);
return 0;
}
Bình luận