Hướng dẫn giải của [VTT Q4 Contest 05] Bài 4: Ước chung lớn nhất [GCD]
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
Trong mọi đoạn liên tiếp gồm ~k~ phần tử, tìm đoạn có ước chung lớn nhất (gcd) lớn nhất. Cần tính gcd của rất nhiều đoạn cùng độ dài nên ta dùng cấu trúc cho phép hỏi nhanh.
Sub 1: Tính trực tiếp — ~O(n \cdot k)~, dùng khi ~n \le 1000~
Với mỗi vị trí đầu ~i~, tính gcd của ~k~ phần tử bằng vòng lặp rồi lấy max. Nếu chỉ nộp sub này: đúng 14/20 test.
Sub 2: Bảng thưa gcd — ~O(n \log n)~
Gọi ~sp[j][i]~ là gcd của ~2^j~ phần tử bắt đầu tại ~i~, với ~sp[j][i] = \gcd(sp[j-1][i], sp[j-1][i+2^{j-1}])~. Với đoạn độ dài ~k~, đặt ~lg = \lfloor \log_2 k \rfloor~, gcd của đoạn bằng gcd của hai khối độ dài ~2^{lg}~ ở đầu và cuối đoạn; hai khối chồng nhau không làm sai vì gcd không bị ảnh hưởng khi lặp lại phần tử. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu, nếu ~n \le 1000~ 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 n, k;
int a[100005];
int sp[17][100005];
// Sub 1: với mỗi đoạn k phần tử tính gcd trực tiếp — O(n*k)
void sub1() {
int ans = 0;
for (int i = 0; i + k <= n; i++) {
int g = 0;
for (int j = i; j < i + k; j++) g = __gcd(g, a[j]);
ans = max(ans, g);
}
cout << ans << "\n";
}
// Sub 2: bảng thưa (sparse table) cho gcd, truy vấn mỗi đoạn O(1) phép gcd — O(n log n)
void sub2() {
for (int i = 0; i < n; i++) sp[0][i] = a[i];
for (int j = 1; (1 << j) <= n; j++)
for (int i = 0; i + (1 << j) <= n; i++)
sp[j][i] = __gcd(sp[j - 1][i], sp[j - 1][i + (1 << (j - 1))]);
int lg = 31 - __builtin_clz(k);
int ans = 0;
for (int i = 0; i + k <= n; i++)
// gcd chịu được hai đoạn chồng nhau
ans = max(ans, __gcd(sp[lg][i], sp[lg][i + k - (1 << lg)]));
cout << ans << "\n";
}
int main() {
freopen("GCD.INP", "r", stdin);
freopen("GCD.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 1000) sub1();
else sub2();
}
Bình luận