Hướng dẫn giải của Tổng ước chung lớn nhất (đề THCS Phú Thọ 2023-2024)
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~ để ~GCD(a_i, a_j) + GCD(a_k, a_t)~ lớn nhất. Nhận xét: hai cặp nằm ở hai phía của một điểm cắt ~p~ (cặp thứ nhất trong ~a[1..p]~, cặp thứ hai trong ~a[p+1..n]~), nên đáp án là ~\max_p (pre_p + suf_{p+1})~ với ~pre_p~ là GCD lớn nhất của một cặp trong ~a[1..p]~ và ~suf_p~ là GCD lớn nhất của một cặp trong ~a[p..n]~.
Sub 1: Vét cạn — ~O(n^4)~, dùng khi ~n \le 50~
Thử mọi bộ 4 chỉ số. Nếu chỉ nộp sub này: đúng 6/20 test.
Sub 2: Tách điểm cắt — ~O(n^2 \log A)~, dùng khi ~n \le 1000~
Tính GCD mọi cặp, ghi lại giá trị lớn nhất của cặp kết thúc tại ~j~ và cặp bắt đầu tại ~i~, từ đó lập ~pre~, ~suf~ rồi duyệt điểm cắt. Nếu chỉ nộp sub này: đúng 12/20 test.
Sub 3: Duyệt theo ước — ~O(n \sqrt{A})~
Khi thêm ~a_p~, GCD lớn nhất với các số đứng trước chính là ước ~d~ lớn nhất của ~a_p~ mà đã có số trước đó chia hết cho ~d~ (mảng đếm ~cnt[d]~ số phần tử đã gặp chia hết cho ~d~). Duyệt ước của ~a_p~ theo căn, cập nhật ~cnt~, nhờ đó lập ~pre~ trong thời gian gần tuyến tính; tương tự duyệt ngược để lập ~suf~. Nộp riêng sub này đú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. Chương trình đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100005];
int pre[100005], suf[100005]; // pre[p]: gcd cặp lớn nhất trong a[1..p]; suf[p]: trong a[p..n]
int cnt[100005];
// Sub 1: vét cạn 4 chỉ số i<j<k<t, 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: tính gcd mọi cặp O(n^2 log), rồi tách theo điểm cắt p: đáp án = max pre[p] + suf[p+1]. Dùng khi n <= 1000
void sub2() {
vector<int> m(n + 2, 0), m2(n + 2, 0);
for (int j = 1; j <= n; j++)
for (int i = 1; i < j; i++) {
int g = __gcd(a[i], a[j]);
m[j] = max(m[j], g); // cặp kết thúc tại j
m2[i] = max(m2[i], g); // cặp bắt đầu tại i
}
pre[0] = 0;
for (int p = 1; p <= n; p++) pre[p] = max(pre[p - 1], m[p]);
suf[n + 1] = 0;
for (int p = n; p >= 1; p--) suf[p] = max(suf[p + 1], m2[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: cùng ý tưởng cắt đôi, nhưng gcd lớn nhất của a[p] với các số đứng trước tìm qua các ước:
// ước d lớn nhất của a[p] đã xuất hiện (cnt[d] > 0). Mỗi số có ít ước nên O(n sqrt(A))
void sub3() {
pre[0] = 0;
for (int p = 1; p <= n; p++) {
int best = pre[p - 1];
vector<int> ds;
for (int d = 1; d * d <= a[p]; d++)
if (a[p] % d == 0) {
ds.push_back(d);
if (d * d != a[p]) ds.push_back(a[p] / d);
}
for (int d : ds) if (cnt[d] > 0) best = max(best, d);
for (int d : ds) cnt[d]++;
pre[p] = best;
}
memset(cnt, 0, sizeof(cnt));
suf[n + 1] = 0;
for (int p = n; p >= 1; p--) {
int best = suf[p + 1];
vector<int> ds;
for (int d = 1; d * d <= a[p]; d++)
if (a[p] % d == 0) {
ds.push_back(d);
if (d * d != a[p]) ds.push_back(a[p] / d);
}
for (int d : ds) if (cnt[d] > 0) best = max(best, d);
for (int d : ds) cnt[d]++;
suf[p] = best;
}
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