백준9537 잘생긴 GCD

작성일 | In

문제 링크

  • http://icpc.me/9537

문제 출처

  • 2013 CERC C번

사용 알고리즘

  • 분할정복

시간복잡도

  • $O(N \log N)$

풀이

모든 구간을 확인해야 하므로 분할 정복을 생각해봅시다. 구체적으로, 어떤 $m$에 대해 $A[m]$을 지나는 모든 구간들 중 잘생긴 GCD의 최댓값을 구할 수 있어야 합니다.

가장 먼저 생각해볼 수 있는 방법은, 왼쪽 방향으로 $(A[m], 1), (\text{gcd}(A[m-1\cdots m]), 2), \cdots (\text{gcd}(A[1\cdots m]), m)$을, 오른쪽 방향으로 $(A[m], 1), (\text{gcd}(A[m\cdots m+1]), 2), \cdots (\text{gcd}(A[m\cdots N]), N-m+1)$을 구한 뒤, 2중 반복문을 이용해 모든 구간을 보는 방법이 있습니다. 이때의 시간 복잡도는 $O(N^2)$이므로 $T(N) = 2T(N/2) + O(N^2) = O(N^2)$이 됩니다.

이 풀이의 연산량을 줄이는 방법은 무엇이 있을까요? 각 방향으로 순서쌍을 구할 때, gcd값이 같다면 $m$에서 가장 멀리 떨어진 지점만 저장하는 방식으로 커팅을 할 수 있습니다. 그리고 이 커팅을 적용하면 AC를 받을 수 있습니다.
그 이유는, gcd가 바뀔 때마다 매번 2배 이상 줄어들기 때문에 서로 다른 gcd값만 저장하면 $O(\log X)$개만 저장됩니다. 그러므로 시간 복잡도는 $T(N) = 2T(N/2) + O(N + \log^2 N) = T(N \log N)$이 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using PLL = pair<ll, ll>;

ll N, A[101010], R;

void Solve(int s, int e){
    if(s >= e){ R = max(R, A[s]); return; }
    int m = s + e >> 1;
    Solve(s, m-1);
    Solve(m+1, e);

    vector<PLL> l, r;
    l = r = vector<PLL>{ {A[m], m} };
    for(int i=m-1; i>=s; i--){
        ll g = __gcd(l.back().x, A[i]);
        if(g == l.back().x) l.back().y = i;
        else l.emplace_back(g, i);
    }
    for(int i=m+1; i<=e; i++){
        ll g = __gcd(r.back().x, A[i]);
        if(g == r.back().x) r.back().y = i;
        else r.emplace_back(g, i);
    }
    for(auto i : l) for(auto j : r) R = max(R, __gcd(i.x, j.x) * (j.y - i.y + 1));
}

void Solve(){
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    R = 0; Solve(1, N);
    cout << R << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T; while(T--) Solve();
}