1. 문제 설명 📌

(1) 링크🔗

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

(2) 해설🕵

입력으로 주어지는 A와 B는 1로 이루어진 숫자의 길이인데, 그 길이가 $2^{63}$으로 너무 길다. 분명 이 A와 B까지는 Long 자료형으로 표현할 수 있겠으나, 그것이 실제 가리키는 1로 이루어진 숫자는 표현하기가 어렵다. (숫자의 길이가 2^{63}이라 BigInteger로도 힘들 듯 하다.) 여기서 주목해야할 점은

1️⃣ 1로만 이루어져 있다.
2️⃣ 문제 제목이 최대공약수 이다.

정도 일 것이다.

2. 생각의 흐름: 코드가 나오기까지 🗃️

(1) IDEA 도출💡

KEY WORD: 문자열 GCD

임의의 문자열 A,B가 특정 문자열 패턴 P의 반복으로 이루어져 있을 경우, 둘의 최대 공약수 문자열의 길이는 $A = n * P$, $B = m * P$ 일 때, GCD(n,m)이다.

최대 공약수 문자열 이란?
임의의 문자열 A,B가 특정한 문자열 패턴 P의 반복으로 이루어져 있을 때, 두 A,B를 반복으로 만들 수 있는 문자열 중 길이가 가장 긴 것을 말한다.

이것을 설명한 이유는 A,B가 1로만 이루어진 수이기에, A, B를 패턴 1의 반복으로 이루어진 문자열로 봐도 되기 때문이다. 두 수의 공약수는 어떤 형태인가, 공약수의 모습 또한 1의 반복으로 이루어진 문자열의 형태이다. 예제 2를 보면, 111111과 111의 공약수를 구해야 하는데, 111111은 111로 2번 나누어지고, 111은 111 한 번으로 나누어지기에, 둘의 공약수엔 111이 있음을 알 수 있다. 이는 마치 토막 내기와 같다. 다음은 두 문자열의 길이가 18,12일 때 최대 공약수 문자열을 찾아보겠다.

두 수를 11111로 토막 내보니, 낱개가 남았다. 고로 11111은 공약수가 아니다.

길이 6은 두 문자열을 낱개 없이 나눴다. 따라서 111111은 두 수의 공약수이고, 이보다 큰 수가 없으므로 최대 공약수가 된다.

눈치챘는가?
1로 이루어진 두 문자열 사이의 최대 공약수의 길이는 두 수의 길이의 최대공약수와 같다. 이 성질을 이용해 문제를 풀면 된다.

(2) SUDO CODE 📜

1️⃣ 두 문자열의 길이 A, B의 최대 공약수를 구한다.
2️⃣ 최대공약수의 수만큼 StringBuilder에 1을 추가하여 해당 길이로 이루어진 1로 이루어진 문자열을 만들어 출력한다.

(3) 시간복잡도 분석 🕓

유클리드 호제법의 시간 복잡도는 $O(log N)$이다. N의 최대값은 $2^{63}$이다.

3. 구현 코드 🔎

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


public class Main {

    /*
    *  b 1850 최대 공약수
    *  우리가 구해야 할 두 수의 길이를 뜻하는 A,B의 공약수 G가 답이 되는 1들의 길이
    * */

    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());
        Long R = GCD(A,B);
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < R; i++) {
            ans.append(1);
        }
        System.out.println(ans);
    }

    public static Long GCD(Long A, Long B) {
       Long R = A%B;
       while (R != 0) {
           A = B;
           B = R;
           R = A%B;
       }
       return B;
    }
}