[java] 백준 1850번 문제(최대 공약수 구하기)

원본 링크 : https://www.acmicpc.net/problem/1850

---

문제설명

 

 

소스코드

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

public class Boj_1850
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());

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

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

 

설명

• 유클리드 호제법을 사용한다.
• a와 b의 최대 공약수 만큼 1을 반복적으로 출력하면 정답이 된다.