[백준] 1850 : 최대공약수 JAVA 풀이

 

A와 B를 구성하는 1의 개수가 입력된다.

이때 입력되는 수는 2^63-1까지라서 long으로 입력받아야 한다.

 

입력된 수만큼 1을 반복한 수들의 최대공약수를 구하면 되겠지.라고 생각하기 쉽지만

여기서 문제가 발생할 수 있다.

만약 2^60이 입력된다면, 1을 2^60번만큼 반복한 수를 담을 수 있는 자료형은 존재하지 않는다.

예제 입력 3번이 여기에 해당한다.

 

그럼 어떻게 해야 하는가..

예제 입력을 잘 보면 규칙을 찾을 수 있다.

 

3과 4의 최대공약수는 1이고

111과 1111의 최대공약수는 1이다.

 

3과 6의 최대공약수는 3이고

111과 111111의 최대공약수는 111이다.

 

500000000000000000 500000000000000002의 최대공약수는 2이다.

1이 500000000000000000번 반복된 수와 500000000000000002번 반복된 수의 최대공약수는 몇일까?

아마 11일 것이다.

왜 그런지는 3과 4, 3과 6의 예시를 잘 보면 알 수 있다.

 

즉 입력된 두 수의 최대공약수를 찾고 그만큼 1을 반복하면 되는 것이다.

 

 

import java.io.*;
import java.util.*;
public class Main {

	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		long a = Long.parseLong(st.nextToken());
		long b = Long.parseLong(st.nextToken());
		
		String s = "1";
		
		System.out.println(s.repeat((int)gcd(a,b)));
		
	}
	static long gcd(long a, long b) {
		while(b!=0) {
			long r = a % b;
			
			a = b;
			b = r;
		}
		return a;
	}

}