[BOJ] 1850 - 최대공약수 JAVA

www.acmicpc.net/problem/1850

1850번: 최대공약수

문제

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

입력

첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 263보다 작은 자연수이다.

출력

첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다.

예제 입력 1

3 4

예제 출력 1

1

예제 입력 2

3 6

예제 출력 2

111

예제 입력 3

500000000000000000 500000000000000002

예제 출력 3

11

 

 

 

 

 

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static long gcd(long a, long b) {
        if(b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());

        long gcd = gcd(a, b);
        for(int i = 0; i < gcd; i++) {
            sb.append("1");
        }
        System.out.println(sb.toString());
    }
}

 

함정이다.

 

입력받은 1의 개수만큼 1을 이어붙인 숫자를 만들어서 GCD를 구하려고 했다.

이렇게 하려면 예제 입력 3번의 경우에는 도저히 숫자를 만들어낼 수가 없다.
(50경자리 숫자를 어떻게 만들어..)

 

정답 코드를 찾아보니,

1의 개수끼리 GCD를 구하면 그게 그 수의 GCD에 들어있는 1의 개수가 된단다.

 

왜인지는 모르겠다. 편하게 이해하기엔 수학적 머리가 너무 딸린다.

 

알고 싶지도 않다.