Hướng dẫn giải của Dãy số đặc biệt (đề HSG 9 Phú Thọ 2024-2025)
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
Số ~x~ là đặc biệt nếu tổng các ước của ~x~ chia hết cho 3. Mỗi câu hỏi ~(l, r, k)~ hỏi số phần tử đặc biệt trong đoạn ~a_l..a_r~ có ~\ge k~ không.
Sub 1: Vét cạn — ~O(n \sqrt{A} + n \cdot q)~, dùng khi ~n, q \le 1000~
Tính tổng ước từng ~a_i~ bằng thử chia đến căn, đánh dấu số đặc biệt; mỗi câu hỏi duyệt đoạn ~[l, r]~ để đếm. Nếu chỉ nộp sub này: đúng 19/20 test (1 test quá thời gian).
Sub 2: Sàng + cộng dồn — ~O(A \log A + n + q)~
Sàng tổng ước theo modulo 3 cho mọi số đến ~\max a_i~ (với mỗi ~d~ cộng ~d~ vào các bội của nó), rồi mảng cộng dồn số phần tử đặc biệt, mỗi câu hỏi trả lời ~O(1)~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Lưu ý: một số test (1, 7, 9) có ít dòng truy vấn hơn ~q~ (file bị thiếu vài dòng cuối) nhưng đáp án vẫn có đủ ~q~ dòng. Chương trình đọc truy vấn vào các biến ~l, r, k~ dùng lại, nên khi hết dữ liệu thì truy vấn cuối được lặp lại; cách này khớp đáp án. Với dữ liệu đúng đề thì không ảnh hưởng.
Chương trình đọc dữ liệu; ~n, q \le 1000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<long long> a; // a[1..n]
vector<array<long long, 3>> qs; // câu hỏi (l, r, k)
// Tổng các ước của x (vét cạn theo i <= sqrt(x))
long long sigma(long long x) {
long long s = 0;
for (long long i = 1; i * i <= x; i++)
if (x % i == 0) {
s += i;
if (i != x / i) s += x / i;
}
return s;
}
// Sub 1: vét cạn — xét từng a_i có phải số đặc biệt, mỗi câu hỏi đếm trực tiếp trên đoạn. O(n*q)
void sub1() {
vector<int> sp(n + 1, 0);
for (int i = 1; i <= n; i++) sp[i] = (sigma(a[i]) % 3 == 0) ? 1 : 0;
for (auto &t : qs) {
int cnt = 0;
for (long long i = t[0]; i <= t[1]; i++) cnt += sp[i];
cout << (cnt >= t[2] ? "YES" : "NO") << "\n";
}
}
// Sub 2: sàng tổng ước theo modulo 3 cho mọi số đến max a_i, rồi cộng dồn số lượng số đặc biệt.
// Mỗi câu hỏi trả lời trong O(1).
void sub2() {
long long M = 0;
for (int i = 1; i <= n; i++) M = max(M, a[i]);
vector<int> s(M + 1, 0); // s[x] = (tổng ước của x) mod 3
for (long long d = 1; d <= M; d++)
for (long long m = d; m <= M; m += d)
s[m] = (int)((s[m] + d) % 3);
vector<int> pre(n + 1, 0);
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + (s[a[i]] == 0 ? 1 : 0);
for (auto &t : qs) {
int cnt = pre[t[1]] - pre[t[0] - 1];
cout << (cnt >= t[2] ? "YES" : "NO") << "\n";
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
a.assign(n + 1, 0);
for (int i = 1; i <= n; i++) cin >> a[i];
qs.resize(q);
long long l = 1, r = 1, k = 1; // nếu file thiếu dòng truy vấn thì giữ giá trị truy vấn trước đó
for (auto &t : qs) {
cin >> l >> r >> k;
t = {l, r, k};
}
if (n <= 1000 && q <= 1000) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
return 0;
}
Bình luận