[BOJ 26092 // C++] 수학적인 최소 공통 조상

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 26092번 문제인 수학적인 최소 공통 조상이다.
문제는 아래 링크를 확인하자.

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

 

두 정점 번호 \(x\)와 \(y\)가 가리키는 두 정점의 LCA(최소 공통 조상)는 \(x\)와 \(y\)의 공약수 중 하나가 될 것임은 쉽게 관찰할 수 있다. 이로부터, \(x\)와 \(y\)의 소인수 중 공약수에 포함될 수 없는 소인수가 모두 없어지기 전까지는 부모 정점으로 거슬러 올라가는 것을 반복해야 할 것임을 발견할 수 있다. 또한 각 정점에서 부모 정점으로 이동할 때 번호는 가장 작은 소인수부터 사라지므로, \(x\)와 \(y\)에 대하여 소인수 중 공약수에 포함되지 않는 최대의 소인수 '미만'의 모든 소인수는 지워야 함을 알 수 있다. 또한 공약수에 포함되지 않는 최대 소인수는 \(x\)와 \(y\)의 공약수에 포함된 개수만큼 남기고 나머지는 지워야 함을 알 수 있다.

 

위 과정에서 정점을 거슬러올라가는 총 횟수는 \(\lg{A}+\lg{B}\)  이하이므로 위와 같은 풀이를 통해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <utility>
using namespace std;
typedef long long ll;

ll A, B;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> A >> B;
	if (A < B) swap(A, B);
	for (ll i = 2; i < 1000001; i++) {
		if (A == B) {
			cout << A;
			return 0;
		}
		if (A % i == 0) A /= i;
		else if (B % i == 0) B /= i;
		else i++;
		i--;
		if (A < B) swap(A, B);
	}

	cout << 1;
}