[BOJ/JAVA] 백준 2824 : 최대공약수 (자바)

문제 정보

  문제명   - 최대공약수
  난이도   - 골드 V
문제 번호 - 2824번

---

문제 링크

BOJ_G5_2824_최대공약수

2824번: 최대공약수

---

문제

상근이는 학생들에게 두 양의 정수 A와 B의 최대공약수를 계산하는 문제를 내주었다. 그런데, 상근이는 학생들을 골탕먹이기 위해 매우 큰 A와 B를 주었다.
상근이는 N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 된다.
이 수가 주어졌을 때, 최대공약수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다.
둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다.
셋째 줄에 M(1 ≤ M ≤ 1000)이 주어진다.
넷째 줄에는 M개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, M개의 수를 곱하면 B가 된다.

---

출력

두 수의 최대공약수를 출력한다. 만약, 9자리보다 길다면, 마지막 9자리만 출력한다. (최대 공약수가 1000012028인 경우에는 000012028을 출력해야 한다)

---

예제 입력/출력

예제 입력	예제 출력
3 2 3 5 2 4 5	10
4 6 2 3 4 1 1	1
3 358572 83391967 82 3 50229961 1091444 8863	000012028

---

알고리즘 분류

● 수학
● 구현
● 정수론
● 소수 판정

---

소스코드

package Lv3_Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
 * @author HanHoon
 * @category 수학, 구현, 정수론, 소수 판정
 * https://www.acmicpc.net/problem/2824
 */
public class BOJ_G5_2824_최대공약수 {
	public static long gcd(long a, long b) {
		if(a%b == 0) return b;
		return gcd(b, a%b);
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		// N개의 수
		int N = Integer.parseInt(br.readLine());
		long[] arr1 = new long[N];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++)
			arr1[i] = Long.parseLong(st.nextToken());
		// M개의 수
		int M = Integer.parseInt(br.readLine());
		long[] arr2 = new long[M];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < M; i++)
			arr2[i] = Long.parseLong(st.nextToken());
		// 모든 경우의 수에 대해 진행을 해 최대공배수를 구한다.
		long tmp = 1l;
		for (int i = 0; i < N; i++) {
			if(arr1[i] == 1) continue;
			for (int j = 0; j < M; j++) {
				if(arr2[j] == 1) continue;
				long gcd = gcd(Math.max(arr1[i], arr2[j]), Math.min(arr1[i], arr2[j]));
				tmp *= gcd;
				// 어차피 10자리 이상은 필요 없으므로 오버플로우 방지를 위해 10자리수 이하로 유지한다.
				if(tmp >= 10000000000l)
					tmp %= 10000000000l;
				arr1[i] /= gcd;
				arr2[j] /= gcd;
			}
		}
		String result = tmp + "";
		if(result.length() > 9)
			result = result.substring(result.length()-9);
		System.out.println(result);
		br.close();
	}
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---