최대공약수

문제 링크https://www.acmicpc.net/problem/2609문제 풀이 과정최대공약수와 최소공배수 문제에 대해 효율적으로 풀기 위해서는 유클리드 호제법에 따라 최대공약수를 푸는 방법에 대해 알아야 손쉽게 풀 수 있다.유클리드 호제법이란 2개의 자연수에 대한 최대공약수를 구하는 방식이다. 쉽게 설명하면 두 수 a,b에 대해서 더 작은 수로 나눈 나머지로 끊임없이 0이 될때까지 나누는걸 의미한다. 이걸 쉽게 설명하려면 아래 예시가 가장 쉽게 이해가 된다.더보기1. 1500 ÷ 3261500을 326으로 나눈 몫은 4이고, 나머지는 196이야.즉, 1500 ÷ 326 = 4 (몫), 나머지 1962. 326 ÷ 196이제 326을 196으로 나눠. 몫은 1이고, 나머지는 130이야.즉, 326 ÷..