[BOJ 2824 // C++] 최대공약수

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2824번 문제인 최대공약수이다.
문제는 아래 링크를 확인하자.

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

2824번: 최대공약수

두 수 A와 B를 직접 구하려면 큰 정수의 연산을 직접 구현해야하므로 번거롭다.

대신 각 A와 B를 구성하는 모든 소인수를 직접 구해 공통 소인수들을 곱하는 방식으로 최대공약수를 구해내자.

 

최대공약수를 계산하는 과정에서 그 값이 1,000,000,000을 넘어서는 상황이 발생하는지 체크하는 변수를 하나 만들어 leading zero를 붙여 출력해야하는지의 여부를 판별하고 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int N, M;
vector<int> A, B;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	while (N--) {
		int cur; cin >> cur;
		for (int i = 2; i < 31622; i++) {
			while (cur % i == 0) A.emplace_back(i), cur /= i;
		}
		if (cur > 1) A.emplace_back(cur);
	}

	cin >> M;
	while (M--) {
		int cur; cin >> cur;
		for (int i = 2; i < 31622; i++) {
			while (cur % i == 0) B.emplace_back(i), cur /= i;
		}
		if (cur > 1) B.emplace_back(cur);
	}

	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	
	bool overflowed = 0;
	ll ans = 1;

	while (!A.empty() && !B.empty()) {
		if (A.back() > B.back()) A.pop_back();
		else if (A.back() < B.back()) B.pop_back();
		else {
			ans *= A.back();
			if (ans > 999999999) ans %= 1000000000, overflowed = 1;
			A.pop_back(), B.pop_back();
		}
	}

	if (overflowed) {
		if (ans < 100000000) cout << 0;
		if (ans < 10000000) cout << 0;
		if (ans < 1000000) cout << 0;
		if (ans < 100000) cout << 0;
		if (ans < 10000) cout << 0;
		if (ans < 1000) cout << 0;
		if (ans < 100) cout << 0;
		if (ans < 10) cout << 0;
	}

	cout << ans;
}