백준 26092, 수학적인 최소 공통 조상

개요

문제 링크
골드 4, 정수론
두 정수를 가장 작은 소인수로 나눌 때 같아지는 지점 구하기

---

접근

1. LCA에 익숙한 사람은 최소공통조상이라는 말이 익숙했을 것이다. 딱히 관련은 없다.
2. 가장 작은 소인수로 나눠가는데, 한 지점으로 같아지면, 그 이후부터는 소인수가 계속 같을 것이다. 또한 나누어준 소인수는 항상 오름차순이다.
3. 두 수를 소인수분해를 하고 순서대로 정렬을 한다. 그리고 가장 긴 뒷꼬리의 곱을 구해주면 된다. N이 크니까 체를 만들고 코드를 짜주자.

---

Pseudo code

// 체 만들기
p = make_eras()
vector fraction(a) {
    vector frac
    for (auto x:p)
        while (a%x == 0)
            a /= x, frac += x
    // 뒤집어서 앞에서부터 봐준다
    return reverse(frac)
}

a = fraction(a)
b = fraction(b)
while(a[i] == b[i])
    answer *= a[i]

---

Source code

#include <iostream>
#include <algorithm>
using namespace std;

using ld = long long;
typedef vector<ld> vec;

#define P 1000000
bool t[P];
vec p;

vec frac(ld a) {
    vec x;
    for (auto q:p)
        while(a%q==0 && a) {
            a /= q;
            x.push_back(q);
        }
    if (1<a) x.push_back(a);
    reverse(x.begin(), x.end());
    return x;
}

int main() {
    for (ld i=2; i<P; i++)
        if (!t[i]) {
            p.push_back(i);
            for (ld j=i*i; j<P; j+=i)
                t[j] = 1;
        }
    ld a, b;
    cin>>a>>b;
    vec x, y;
    x = frac(a), y = frac(b);
    ld n = min(x.size(), y.size());
    ld v = 1;
    for (int i=0; i<n; i++)
        if (x[i]==y[i])
            v *= x[i];
        else
            break;
    cout << v;
}