BOJ 26092: 수학적인 최소 공통 조상 [Python 3]

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

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

오늘의 문제는 수학적인 지식 (공약수)를 이용하여 푸는 문제였다.

설명은 어려워 보이지만, 간단히 설명하면

가령 36이라는 수가 있다.

36의 약수는 1,2,3,4,6,9,12,18,36가 있다.

그렇기에 36의 부모 노드는 2 이상의 약수 중 제일 작은 2로 나눈 수이다. (18)

해당 법칙을 이용하여 계속 나타내면

36-> 18 -> 9 -> 3 -> 1

이런식으로 부모노드가 이어진다.

 

def factorization(n):
    d=2
    factors=[]
    while d<=int(n**0.5)+1:
        if not n%d:
            factors.append(d)
            n/=d
        else:
            d+=1
    return factors

a,b=map(int,input().split())
aList,bList=[a],[b]
for i in factorization(a):
    aList.append(a//i)
    a/=i
for i in factorization(b):
    bList.append(b//i)
    b/=i
aList=list(map(int,aList))
bList=list(map(int,bList))
print(max(list(set(aList)&set(bList))))

factorization이라는 함수는 소인수분해를 하는 함수이다.

소인수들을 list로 return한다.

a,b 두 수를 입력받고, aList랑 bList에 자기 자신을 넣어놓는다. 

그 다음, 아까 설명했던 방식으로 계속 나눠주고, list에 넣는다.

마지막 줄은 

두 list의 공통 수들을 찾는 방법이다. (교집합)

list(set(aList)&set(bList))