Hướng dẫn giải của [VTT Q4 Contest 03] Bài 3: Tổng ướ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
Cần chọn hai cặp chỉ số không giao nhau và cặp thứ nhất nằm hoàn toàn trước cặp thứ hai, sao cho tổng hai ước chung lớn nhất lớn nhất. Ý chính: cắt dãy làm hai phần, mỗi phần chọn cặp có gcd lớn nhất.
Sub 1: Vét cạn bốn chỉ số — ~O(n^4)~, dùng khi ~n \le 50~
Thử mọi bộ ~i < j < k < t~, tính hai gcd và lấy tổng lớn nhất. Nếu chỉ nộp sub này: đúng 6/20 test.
Sub 2: Tiền tố và hậu tố — ~O(n^2 \log A)~, dùng khi ~n \le 1000~
Gọi ~pre[m]~ là gcd lớn nhất của một cặp trong ~m~ phần tử đầu, ~suf[m]~ là gcd lớn nhất của một cặp trong các phần tử từ ~m~ trở đi. Tính bằng cách thử mọi cặp. Đáp án là ~\max(pre[m] + suf[m+1])~ với ~m~ từ 2 đến ~n-2~. Nếu chỉ nộp sub này: đúng 12/20 test.
Sub 3: Đếm ước — ~O(A \log A)~
Để tính ~pre~ nhanh hơn, giữ ~cnt[d]~ là số phần tử đã gặp chia hết cho ~d~. Khi thêm phần tử ~x~, với mỗi ước ~d~ của ~x~ mà ~cnt[d] > 0~ thì tồn tại một cặp có gcd ít nhất ~d~ (và gcd thực sự cũng là một ước chung nên cách tính này không vượt giá trị đúng). Lấy ~d~ lớn nhất rồi cập nhật ~cnt~. Danh sách ước của mọi số đến ~10^5~ được lập bằng sàng. Làm tương tự cho hậu tố. Đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc dữ liệu; ~n \le 50~ gọi sub1, ~n \le 1000~ gọi sub2, còn lại gọi sub3. 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;
const int MX = 100005;
int n;
int a[MX];
// Sub 1: vét cạn bốn chỉ số — O(n^4), dùng khi n <= 50
void sub1() {
int best = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int g1 = __gcd(a[i], a[j]);
for (int k = j + 1; k < n; k++)
for (int t = k + 1; t < n; t++)
best = max(best, g1 + __gcd(a[k], a[t]));
}
cout << best << "\n";
}
// Sub 2: pre[m] = gcd lớn nhất của một cặp trong m phần tử đầu, suf[m] tương tự cho đoạn cuối — O(n^2 log)
void sub2() {
vector<int> pre(n + 2, 0), suf(n + 2, 0);
for (int m = 1; m <= n; m++) {
pre[m] = pre[m - 1];
for (int i = 1; i < m; i++) pre[m] = max(pre[m], __gcd(a[i - 1], a[m - 1]));
}
for (int m = n; m >= 1; m--) {
suf[m] = suf[m + 1];
for (int i = m + 1; i <= n; i++) suf[m] = max(suf[m], __gcd(a[i - 1], a[m - 1]));
}
int best = 0;
for (int m = 2; m + 2 <= n; m++) best = max(best, pre[m] + suf[m + 1]);
cout << best << "\n";
}
// Sub 3: cnt[d] = số phần tử đã gặp chia hết cho d. Thêm x: nếu cnt[d] > 0 với d | x thì có cặp gcd >= d — O(A log A)
vector<int> divs[MX];
void sub3() {
int A = *max_element(a, a + n);
for (int d = 1; d <= A; d++)
for (int m = d; m <= A; m += d) divs[m].push_back(d);
vector<int> pre(n + 2, 0), suf(n + 2, 0), cnt(A + 1, 0);
for (int m = 1; m <= n; m++) {
pre[m] = pre[m - 1];
for (int d : divs[a[m - 1]]) {
if (cnt[d] > 0) pre[m] = max(pre[m], d);
cnt[d]++;
}
}
fill(cnt.begin(), cnt.end(), 0);
for (int m = n; m >= 1; m--) {
suf[m] = suf[m + 1];
for (int d : divs[a[m - 1]]) {
if (cnt[d] > 0) suf[m] = max(suf[m], d);
cnt[d]++;
}
}
int best = 0;
for (int m = 2; m + 2 <= n; m++) best = max(best, pre[m] + suf[m + 1]);
cout << best << "\n";
}
int main() {
freopen("GCD.INP", "r", stdin);
freopen("GCD.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 50) sub1();
else if (n <= 1000) sub2();
else sub3();
}
Bình luận