Editorial for Bedao Regular Contest 01 - GCDMAX
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Nhận xét: Đề bài yêu cầu ta tìm ~GCD~ lớn nhất có thể của ~n-1~ phần tử còn lại khi bỏ một phần tử đi. Qua đó khi duyệt trâu bài toán, độ phức tạp lớn sẽ dấn đến TLE.
Độ phức tạp: : ~O(n^2 + n\log{\max a_i})~
Trước khi tối ưu hóa thời gian chạy, chúng ta cần biết một tính chất của ~GCD~: ~\gcd(a,\gcd(b,c))= \gcd(\gcd(a,b) ~~,c))~ và ~GCD~ càng duy trì trên đoạn ~[l,r]~ dài sẽ càng có xu hướng nhỏ đi.
Qua đó ta rút ra nhận xét: ~\gcd(a_1,a_2,…a_{i-1},a_{i+1}...,a_n)~ = ~\gcd(\gcd_{j=1}^{i - 1} a_j,~ ~ \gcd_{j=i + 1}^{n} a_j))~ (chú ý trường hợp n = 1)
Kết luận: Để tối ưu hóa thời gian chạy, ta tính ~GCD~ của tất cả ~prefix~ và ~suffix~. Nói cách khác, ~{prefix}_i = \gcd_{j=1}^{i} a_j~ và ~{suffix}_i = \gcd_{j=i}^{n} a_j~. Khi đó kết quả lớn nhất ta cần tìm là: ~\gcd({suffix}_{i-1},{prefix}_{i+1})~ ~,i \in [1,n]~.
Độ phức tạp: ~O(n\log{\max a_i})~
Code mẫu
/*#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma")*/ // only when really needed /* GNU G++17 7.3.0: No long long for faster code GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */ #include <bits/stdc++.h> #define for1(i,a,b) for (int i = a; i <= b; i++) #define for2(i,a,b) for (int i = a; i >= b; i--) #define int long long #define sz(a) (int)a.size() #define pii pair<int,int> #define pb push_back /* __builtin_popcountll(x) : Number of 1-bit __builtin_ctzll(x) : Number of trailing 0 */ #define PI 3.1415926535897932384626433832795 #define INF 1000000000000000000 #define MOD 1000000007 #define MOD2 1000000009 #define EPS 1e-6 using namespace std; int n, a[1000005], pre[1000005], suf[1000005]; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("cf.inp", "r", stdin); // freopen("cf.out", "w", stdout); cin >> n; for1(i,1,n) cin >> a[i]; for1(i,1,n) pre[i] = __gcd(pre[i - 1], a[i]); for2(i,n,1) suf[i] = __gcd(suf[i + 1], a[i]); int res = 0; for1(i,1,n) res = max(res, __gcd(pre[i - 1], suf[i + 1])); if (n == 1) cout << 1000000000; else if (n == 2) cout << max(a[1], a[2]); else cout << res; }
Comments