최대 공약수, 최소 공배수 알고리즘

기존의 그냥 하나씩 대입해서 최대 공약수는 찾는 알고리즘은 $O(N)$의 시간복잡도를 가진다.

유클리드 호제법을 사용하면 $O(logN)$의 시간복잡도를 가진다.

$A = 204, B = 48$이라고 가정하자.

12가 204와 48의 최대 공약수이다.

왜그럴까?

증명

A와 B의 최대공약수는 B와 r의 최대 공약수와 같다.

A와 B는 최대공약수에 어떤 수를 곱한 수이다.

A와 B의 최대공약수에 곱해져 있는 수들은 서로소여야 한다. (아니면은 최대공약수가 아님)

서로소 : 두 수를 같이 나누어 떨어지는 수가 1밖에 없는 경우

G : 최대 공약수

$A = aG, B = bG$

A를 B로 나누었을때 몫이 q 나머지가 r이라고 할 때

$A = q * B + r$

정리하면

$aG = q * bG + r$

$r = (a - qb)G$