녕의 학습 기록
백준_1850 최대공약수 (유클리드 호제법) 본문
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ_1850_최대공약수 {
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 temp = gcd(a, b);
StringBuilder result = new StringBuilder();
for (long i=0; i<temp; i++) {
result.append('1');
}
System.out.println(result);
}
static long gcd(long a, long b) {
if (b==0) {
return a;
}
return gcd(b, a%b);
}
}
1850번: 최대공약수
모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A
www.acmicpc.net
'Algorithm > Algorithm 문제' 카테고리의 다른 글
백준_18352 특정 거리의 도시 찾기 (BFS) (0) | 2024.02.11 |
---|---|
백준_21568 Ax+By=C (확장 유클리드 호제법) (1) | 2024.02.10 |
백준_1934 최소공배수 (유클리드 호제법) (1) | 2024.02.06 |
백준_11689 GCD(n, k) = 1 (오일러 피 함수) (0) | 2024.02.05 |
백준_1016 제곱ㄴㄴ수 (에라토스테네스의 채) (0) | 2024.02.04 |