2609: 최대공약수와 최소공배수

www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

유클리드 호제법을 사용하여 푼다.

1) 입력받은 두 수 중 큰 수 A,작은 수 B

2) A를 B로 나눈 나머지 R

3) R이 0이면 A는 B로 나눠지므로 최대공약수는 B

4) R이 0이 아니라면 A값은 B로, B값은 R로 변경한 뒤 위 과정 반복

---

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        long num1 = sc.nextLong();
        long num2 = sc.nextLong();
 
        long gcd = get_gcd(Math.max(num1, num2), Math.min(num1, num2));//큰수 앞에,작은 수 뒤에
        long lcm = get_lcm(num1, num2, gcd);
        
        
        System.out.println(gcd);
        System.out.println(lcm);
    }
 
    public static long get_gcd(long a, long b) {
    	if(b==0) return a;
        else return get_gcd(b,a%b);
    }
    
    public static long get_lcm(long a, long b, long gcd) {
        return (a*b)/gcd;
    }
}
//최대 공약수:gcd(greatest common divisior) 

1) 유클리드 호제법

두 정수 a, b의 최대공약수를 G(a, b)라고 하자.

정수 a, b, q r (b ≠ 0)에 대하여 a = bq + r,이면 G(a, b) = G(b, r)가 성립한다.

〈증명〉
G(a, b) = g라고 하자. 최대공약수의 성질에 의해 a = a′g, b = b′g이고 G(a′, b′) = 1이다.
a = bq + r로부터 r = a - bq = g(a′ - b′q) 이고, g는 r의 약수이다.
G(b, r) = g임을 보이기 위해서는 G(b′, a′ - b′q) = 1임을 보이면 된다.

귀류법을 적용하여 결론을 부정해보자.
어떤 정수 d가 존재하여 G(b′, a′ - b′q) =d(≠ 1)라고 하면, b′ = dm, a′ - b′q = dn라고 할 수 있고, a′ = b′q + dn = dmq + dn = d(mq + n) 이므로 G(a′, b′) = 1라는 가정에 모순이다. 따라서 G(b′, a′ - b′q) = 1이므로 G(b, r) = g가 성립한다.

2) 유클리드 호제법의 사용

유클리드 호제법은 큰 수들의 최대공약수를 구할 때 사용할 수 있다.

a = bq + r 에서 r = a - bq 이므로 G(a, b) = G(a, a - bq)이다. 이제 직접 적용을 해보자.
(예) G(180, 200) = G(180, 200 - 180) = G(180, 20) = G(180 - 20 × 8, 20) = G(20, 20) = 20

<<[네이버 지식백과] 유클리드 호제법 (통합논술 개념어 사전, 2007. 12. 15., 한림학사)>>