백준 BOJ 2824 최대공약수

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

2824번: 최대공약수

문제 해설

10억 이하의 수가 최대 1,000개 곱한 수 A, B가 주어질 때, A와 B의 최대 공약수를 구하는 문제다.

주어진 수를 모두 곱하면 int는 물론 long long 자료형의 범위도 벗어나게 되므로 다 곱해서 해결하기엔 무리가 있다.

공약수를 어떻게 구할까?

 

A/B를 단순화시킨다고 생각해보자.

우리는 보통 분수를 단순화 시킬 때, 분자와 분모 각각을 나머지 없이 나눌 수 있는 수로 나누는 작업을 계속하게 된다.

ex) 54/36 => 27/18 => 9/6 => 3/2 과정을 살펴보면 순서대로 2, 3, 3으로 나누었다. 

이때, 2, 3, 3을 모두 곱한 18이 두 수 54와36의 최대공약수다.

 

문제에선 A, B가 되기위해 곱해야 하는 수들을 친절히 나열해 주었다.

우리는 A에 속한 수들과 B에 속한 수들을 하나하나 매칭 하며 각각의 쌍에 대한 최대공약수를 구하고,

 결과로 나온 여러 최대공약수들을 모두 곱하면 A, B의 최대 공약수가 된다.

 

A에 최대 1,000개의 수, B에 최대 1,000개의 수를 할당하므로 모든 쌍의 수는 100만이다.

충분히 계산 가능하다.

 

 9자리보다 길다면, 마지막 9자리만 출력하라고 했다.

우리는 최대 10자리까지만 구하고 마지막 9자리만 출력하면 된다.

이 과정은 10,000,000,000(100억)으로 나눈 나머지를 구해 처리할 수 있다.

 

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)

using namespace std;

#include <vector>
#include <string>
int GCD(int& A, int& B){
	int tmp_A = A; 
	int tmp_B = B;
	if(tmp_A == tmp_B){
		A = 1, B = 1;
		return tmp_A;
	}
	//
	int big, small;
	if(tmp_A >= tmp_B){
		big = tmp_A; small = tmp_B;
	}else{
		big = tmp_B; small =tmp_A;
	}
	while(big % small != 0){
		int tmp = small;
		small = big % small;
		big = tmp;
	}
	int gcd = small;
	A = A/gcd; B = B/gcd;
	return gcd;
}
int main() {
	fio;
	int N; cin >> N;
	vector<int>vector_N(N, 0);
	for(int i=0; i<N; i++) cin >> vector_N[i];
	int M; cin >> M;
	vector<int>vector_M(M, 0);
	for(int i=0; i<M; i++) cin >> vector_M[i];
	//
	vector<int>vector_com;
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			int gcd = GCD(vector_N[i], vector_M[j]);
			vector_com.push_back(gcd);
		}
	}
	//
	long long answer = 1;
	for(int i=0; i<vector_com.size(); i++){
		answer *= vector_com[i];
		answer %= 10000000000;
	}
	string str_answer = to_string(answer);
	if(str_answer.size() >= 9){
		for(int i=str_answer.size() -9; i<str_answer.size(); i++){
			cout << str_answer[i];
		}
	}else{
		cout << str_answer;
	}
	return 0;
}