Hướng dẫn giải của Ước chung lớn nhất (GCD) (Đề HSG 12 Phú Thọ 2022-2023)
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 hai số khác vị trí trong dãy sao cho ước chung lớn nhất của chúng lớn nhất. Đầu ra là giá trị đó. Đề đọc từ file GCD.INP nhưng máy chấm dùng tên ~gcd.inp~ và ~gcd.out~ (chữ thường), chương trình dùng đúng tên này.
Sub 1: Thử mọi cặp — ~O(n^2 \log V)~, dùng khi ~n \le 1000~
Duyệt mọi cặp ~(i, j)~, lấy ~\gcd(a_i, a_j)~ lớn nhất.
Nếu chỉ nộp sub này: đúng 18/24 test.
Sub 2: Đếm bội — ~O(V \log V)~, với ~V = \max a_i~
Đáp án là số ~d~ lớn nhất sao cho có ít nhất hai số trong dãy chia hết cho ~d~. Vì nếu hai số đó cùng chia hết cho ~d~ thì ~\gcd~ của chúng không nhỏ hơn ~d~. Duyệt ~d~ từ lớn xuống nhỏ, cộng số lượng bội của ~d~ trong mảng đếm, dừng ở ~d~ đầu tiên có số lượng không nhỏ hơn 2.
Nếu chỉ nộp sub này: đúng 24/24 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu rồi chọn sub theo kích thước: dữ liệu nhỏ gọi sub 1 (vét cạn), dữ liệu lớn gọi sub cuối. Khi đi thi, nên nộp đầy đủ như vậy: nếu sub sau sai hoặc chưa kịp làm thì vẫn ăn điểm các sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// Sub 1: vét cạn — thử mọi cặp (i, j), lấy ước chung lớn nhất lớn nhất. O(n^2 log V)
void sub1() {
long long best = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
best = max(best, (long long)__gcd(a[i], a[j]));
cout << best << "\n";
}
// Sub 2: đếm theo ước. Số d là đáp án khi và chỉ khi có ít nhất 2 số trong dãy chia hết cho d
// (hai số đó có ước chung lớn nhất >= d). Duyệt d từ lớn xuống nhỏ, dừng ở d đầu tiên thỏa mãn.
// O(V log V), V = max a_i
void sub2() {
long long V = 0;
for (long long x : a) V = max(V, x);
vector<int> cnt(V + 1, 0);
for (long long x : a) cnt[x]++;
for (long long d = V; d >= 1; d--) {
int c = 0;
for (long long m = d; m <= V; m += d) c += cnt[m];
if (c >= 2) { cout << d << "\n"; return; }
}
}
int main() {
freopen("gcd.inp", "r", stdin);
freopen("gcd.out", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 1000) sub1(); // dữ liệu nhỏ: thử mọi cặp
else sub2();
return 0;
}
Bình luận