BOJ 26092

https://www.acmicpc.net/problem/26092

26092번: 수학적인 최소 공통 조상

 

시간복잡도 훈련에 좋은 문제입니다. 

 

관찰 1. \( n \)의 소인수를 모두 구하는데 걸리는 시간은  \(O(\sqrt{n})\) 입니다.

정수 \(a, b\)에 대해 \(n=ab\)라고 표현할 수 있습니다.  일반성을 잃지 않고 \(a\leq b\) 라고 두면,  

\(n = ab\geq a^2 \) 이므로 \(a\leq \sqrt{n} \) 이 됩니다. 즉, 두 곱으로 쪼갰을 때, 작은 수 \(a \)만 찾으면

나머지 수는 \(n/a \)로 결정됩니다.

 

 

관찰 2. 값 \(n\) 의 조상을 만드는데 걸리는 시간은 \(O(\log_{}{n})\)입니다. 

조상을 만드는 행위는 가장 작은 소인수를 골라 그 값으로 나누는 행위입니다.

나눌 때마다 최소 2이상의 값으로 나눠지니 매 시행마다 최소 절반씩 감소합니다.

따라서 최악의 경우 \(O(\log_{2}{n})\) 시간이 걸립니다.

그리고 조상의 수도 당연히 \(\log_{}{n}\) 개가 됩니다. 

 

따라서  \(O(\sqrt{n})\) 의 시간으로 소인수를 찾고 바로바로 나눠주면서 조상들을 모두 구해줍니다.

가장 작은 소인수부터 나눠주므로 구해지는 조상들을 모으면 내림차순으로 정렬되어 있습니다.

이렇게 두 값 \(p, q\)에 대한 각 조상들을 모은 후 앞에서부터 같은 값이 나오면 끝내주면 됩니다.

조상 수가 적으므로 \(O(|S|^2)\)도 되고, 정렬되어 있으므로 이분탐색으로 \(O(|S|\log_{}{|S|})\)도 됩니다. 

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll>A, B;

// 조상을 모두 찾는 함수 
vector<ll> Find(ll x) {
    vector<ll>par;
    par.push_back(x);
    ll div = 2;
    ll D = sqrt(x);
    while (x && div <= D) {
        if (x % div == 0) {
            x /= div;
            par.push_back(x);
        }
        else div++;
    }
    par.push_back(1);
    return par;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    ll a, b;
    cin >> a >> b;
    A = Find(a), B = Find(b);
    // A를 기준으로 B에 있는 이분탐색 
    for (ll x : A) {
        if (binary_search(B.rbegin(), B.rend(), x)) {
            cout << x << '\n';
            return 0;
        }
    }
}