[Algorithm] 유클리드 호제법

• 두 수의 최대공약수를 구하는 방법 중 하나는 두 수 중 작은 수를 골라 1부터 그 수까지 순차적으로 나눠서 가장 큰 공약수를 알아내는 것이다. 하지만 이 방법은 비효율적이므로, 더 효율적인 방법인 유클리드 호제법을 사용할 수 있다.

• 유클리드 호제법은 두 수의 차와 두 수의 최대 공약수가 동일하다는 원리를 이용한 것으로, 두 수 중 작은 수와 두 수의 차의 최대공약수를 구하는 과정을 반복하면 한 수가 0이 될 때까지 반복적으로 차를 구하면, 다른 한 수가 최대공약수가 된다. 이 방법의 시간복잡도는 O(logN)으로 더 효율적이다.

• 주어진 N개의 수에서 두 개씩 짝지어 그 쌍의 최대공약수를 구하고, 이를 모두 더하는 문제를 해결하기 위해, 모든 수를 vector로 받아 두 수를 인덱싱하여 최대공약수를 구하는 알고리즘을 구현하였다.

• 유클리드 호제법을 이용하여 두 수 A, B의 최대공약수를 G라 하고, 이 두 수의 차를 D라 할 때, a - b와 b가 서로소여야 D와 A 혹은 B의 최대공약수가 동일하다는 것을 증명하였다.