[BOJ2824] 최대공약수

문제 설명

문제 링크

코드 리뷰

입력받은 숫자들을 미리 곱해서 A와 B를 만들면 안된다는 눈치를 문제에서 이미 주었다.

A는 N개의 수의 곱으로 나타나져있고, B는 M개의 수의 곱으로 나타나져있으므로,

각각의 수마다 gcd 즉 최대공약수를 구하는 함수를 통해 gcd를 구하고, 그 값을 ans에 곱해나간다.

ans가 자리수를 초과하게되면 ans에 모듈라연산을 한다.

이 부분에서 미리 모듈라 연산을 해도 상관없을까에 대한 의문이 있었다.

모듈라 연산으로 중간에 ans가 0이되면 이 후에 어떤 gcd를 곱해도 ans는 0이 나오기 때문이었다.

하지만 조금만 생각해보면 상관이 없다는 것을 알게된다.

만약 답 출력 범위가 2자리수였다고 가정해보자.

gcd를 곱해나가던 ans가 100이 되어 모듈라 연산을 통해 ans를 0으로 만들어주건 그냥 100으로 가져가건 우리가 출력해야하는 두자리에 대해선 결국 항상 0이 나오게 된다.

이런식으로 ans범위를 출력범위 이내로 계속 만들어주었다.

import java.io.*;
import java.util.*;

public class BOJ2824_최대공약수 {
	static final int RANGE = 1000000000;
	static int[] aa;
	static int[] ba;
	static int N,M;
	static long ans = 1;
	public static void main(String[] args) throws Exception {
		StringBuilder sb= new StringBuilder();
		StringTokenizer st = null;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		aa = new int[N];
		st = new StringTokenizer(br.readLine());
		boolean flg = false;
		for(int i=0; i<N; i++) {
			aa[i]= Integer.parseInt(st.nextToken());
		}
		M = Integer.parseInt(br.readLine());
		ba = new int[M];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			ba[i]=Integer.parseInt(st.nextToken());
		}
		for(int i=0; i<N; i++) {
			if(aa[i]==1) continue;
			for(int j=0; j<M; j++) {
				if(ba[j]==1) continue;
				int num = gcd(aa[i],ba[j]);
				ans *= num;
				if(ans > RANGE) flg = true;
				ans %= RANGE;
				aa[i] /= num; 
				ba[j] /= num;
			}
		}
		String s = String.valueOf(ans);
		int len = s.length();
		if(len < 9 && flg) {
			for(int i=0; i<9-len; i++) sb.append("0");
		}
		sb.append(ans);
		System.out.println(sb);
	}
	static int gcd(int a, int b) {
		if(b==0) return a;
		return gcd(b, a%b);
	}
}