Hướng dẫn giải của Tin 10 Bài 10: Tổng ước chung lớn nhất
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
Chọn 4 chỉ số ~i<j<k<t~ sao cho ~GCD(a_i,a_j)+GCD(a_k,a_t)~ lớn nhất. Hai cặp nằm hoàn toàn bên trái/bên phải nhau, nên ta chọn một điểm cắt ~p~: cặp thứ nhất nằm trong ~a[1..p]~, cặp thứ hai nằm trong ~a[p+1..n]~.</p>
Sub 1: Vét cạn — ~O(n^4)~, dùng khi ~n \le 50~
Duyệt mọi bộ bốn chỉ số ~i<j<k<t~ và lấy max. Nếu chỉ nộp sub này: đúng 6/20 test.</p>
Sub 2: Tiền tố/hậu tố — ~O(n^2 \log)~, dùng khi ~n \le 1000~
~pre[p]~ là GCD lớn nhất của một cặp trong ~a[1..p]~, ~suf[p]~ là của ~a[p..n]~. Đáp án là ~\max_p (pre[p]+suf[p+1])~. Mỗi ~pre[p]~ tính từ ~pre[p-1]~ và GCD của ~a_p~ với các phần tử trước. Nếu chỉ nộp sub này: đúng 12/20 test.
Sub 3: Đếm ước — ~O(A \log A + n \cdot d)~
Với mỗi phần tử mới ~a_p~, GCD lớn nhất với các phần tử đã xét chính là ước lớn nhất ~d~ của ~a_p~ mà đã có phần tử trước chia hết cho ~d~. Giữ mảng đếm ~cnt[d]~ và duyệt các ước của ~a_p~ từ lớn xuống nhỏ. Danh sách ước của mọi số đến ~10^5~ được tạo bằng sàng. Đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm 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;
int n;
int a[100005];
int pre[100005], suf[100005]; // pre[p] = GCD lớn nhất của một cặp trong a[1..p]; suf[p] tương tự cho a[p..n]
// Sub 1: vét cạn 4 vòng lặp O(n^4) — dùng khi n <= 50
void sub1() {
int best = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
for (int k = j + 1; k <= n; k++)
for (int t = k + 1; t <= n; t++)
best = max(best, __gcd(a[i], a[j]) + __gcd(a[k], a[t]));
cout << best << "\n";
}
// Sub 2: quy hoạch tiền tố/hậu tố, tính GCD từng cặp O(n^2 log) — dùng khi n <= 1000
void sub2() {
for (int p = 1; p <= n; p++) {
pre[p] = pre[p - 1];
for (int j = 1; j < p; j++) pre[p] = max(pre[p], __gcd(a[j], a[p]));
}
suf[n + 1] = 0;
for (int p = n; p >= 1; p--) {
suf[p] = suf[p + 1];
for (int j = p + 1; j <= n; j++) suf[p] = max(suf[p], __gcd(a[j], a[p]));
}
int best = 0;
for (int p = 2; p + 2 <= n; p++) best = max(best, pre[p] + suf[p + 1]);
cout << best << "\n";
}
// Sub 3: như sub 2 nhưng tìm "GCD lớn nhất với các phần tử đã xét" bằng đếm ước
// cnt[d] > 0 nếu có phần tử đã xét chia hết cho d. O(A log A + n * số ước)
vector<int> divs[100005];
int cnt[100005];
void sub3() {
int A = 100000;
for (int d = 1; d <= A; d++)
for (int m = d; m <= A; m += d) divs[m].push_back(d); // divs[m] tăng dần
// tiền tố
for (int p = 1; p <= n; p++) {
pre[p] = pre[p - 1];
for (int k = (int)divs[a[p]].size() - 1; k >= 0; k--) {
int d = divs[a[p]][k];
if (cnt[d]) { pre[p] = max(pre[p], d); break; }
}
for (int d : divs[a[p]]) cnt[d]++;
}
memset(cnt, 0, sizeof cnt);
suf[n + 1] = 0;
for (int p = n; p >= 1; p--) {
suf[p] = suf[p + 1];
for (int k = (int)divs[a[p]].size() - 1; k >= 0; k--) {
int d = divs[a[p]][k];
if (cnt[d]) { suf[p] = max(suf[p], d); break; }
}
for (int d : divs[a[p]]) cnt[d]++;
}
int best = 0;
for (int p = 2; p + 2 <= n; p++) best = max(best, pre[p] + suf[p + 1]);
cout << best << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 50) sub1();
else if (n <= 1000) sub2();
else sub3();
return 0;
}
Bình luận