백준/1850번/Java - 최대공약수

https://www.acmicpc.net/problem/1850

1850번: 최대공약수

---

자리수를 입력받아 모든 자리수가 1로만 이루어진 두 수의 최대 공약수를 구하는 문제.

 

최대 공약수를 구하면 되는 문제이므로 유클리드 호제법을 적용하면 된다는 것을 바로 알 수있다.

 

하지만 문제에서 자리수의 범위가 2의 63제곱 -1 까지 주어졌으므로 직접 두 자연수 A, B를 구해서 문제를 풀 수는 없다.

 

힌트는 자리수가 3, 4인 수, 즉 자리수의 최대 공약수가 1인 두 수의 최대 공약수도 1자리 수라는 것이다.

또한 자리수가 3, 6 즉 자리수의 최대 공약수가 3이므로 두 수의 최대공약수도 3자리수가 된다.

 

1. 따라서 주어진 A, B의 최대 공약수 N을 구한다.

2. 모든 자리수가 1로 이루어진 N 자리수가 정답!

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        long N = Long.parseLong(st.nextToken());
        long M = Long.parseLong(st.nextToken());
        
        //N과 M의 최대 공약수를 구한 뒤 그 수만큼 1을 적어준다.
        long gcd = euclidean(N, M);

        for(long i=0; i<gcd; i++) {
            bw.write("1");
        }

        br.close();
        bw.flush();
        bw.close();
    }

    private static long euclidean(long a, long b) {
        if(a > b) {
            if(a%b == 0) return b;
            else return euclidean(b, (a%b));
        }
        else {
            if(b%a == 0) return a;
            else return euclidean(a, (b%a));
        }
    }
}