[BOJ][🟡4][백준#26092] 수학적인 최소 공통 조상

문제 출처

BAEKJOON Online Judge #26092

문제

$10^{12}$ 개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 $1$번부터 $10^{12}$번까지 번호가 매겨져 있고 $1$번 정점은 루트이다. 이 트리는 다음과 같은 특수한 성질을 가지고 있다.

$2$ 이상 $N$ 이하의 정수 $x$에 대해 $x$의 가장 작은 소인수를 $p$라고 하자. $x$번 정점의 부모 정점은 $\frac{x}{p}$번 정점이다.

두 정점의 가장 가까운 공통 조상은, 두 정점을 모두 자손으로 가지면서 깊이가 가장 깊은 정점으로 정의한다. 두 정수 $a$와 $b$가 주어졌을 때, $a$번 정점과 $b$번 정점의 가장 가까운 공통 조상의 번호를 구해보자.

입력

첫째 줄에 정수 $a$와 $b$가 공백으로 구분되어 주어진다. $(1\leq a,b\leq 10^{12})$

출력

첫째 줄에 $a$번 정점과 $b$번 정점의 가장 가까운 공통 조상의 번호를 출력한다.

예제

예제 1

입력

1 4

출력

1

예제 2

입력

21 49

출력

7

예제 3

입력

30 20

출력

5

My Sol

def check_parent(N):
    S = set([1, N])
    while N > 1:
        flag = 0
        for n in range(2, int(N**(1/2))+1):
            if N%n: continue
            N = N//n
            S.add(N)
            flag = 1
            break
        if not flag: break
    return S

A, B = map(int, input().split())
A_Set = check_parent(A)
B_Set = check_parent(B)
U_Set = A_Set & B_Set
print(max(list(U_Set)))

입력이 10의 12승이므로, 소수판정에서 에라토스테네스의체 알고리즘처럼 제곱근까지 나눠보는 방식을 활용한다. 그렇다면 한 반복당 10의 6승, 즉 100만으로 연산시간 초과를 피할 수 있으며, 최대 100만의 수까지 N을 나눠보며 나누어 떨어지는지 확인한다.

1. 입력을 처리해 두 수를 확인한다.
2. 수를 가장 작은 소인수로 나누며 집합에 넣는다. 부모 정점을 만드는 것이다. 이 부모 정점의 부모 정점을 다시 구해가는 반복을 실시한다.
3. 이 반복은 소인수로 나눌 수 없는 소수가 되거나 1이 되면 종료된다. 이때까지 집합을 구한 뒤 반환한다.
4. 두 수에 대한 부모 정점 집합을 모두 구한 뒤, 교집합을 구한다. 최상위 정점인 1번 정점을 공유하므로 못해도 1번 정점을 가진 교집합이 생긴다. 이 교집합은 공유하는 부모 정점이다.
5. 이 교집합 원소의 최댓값을 구해 출력한다.

결과

맞았습니다!!