백준 2824번 : 최대공약수 (c++)

https://www.acmicpc.net/problem/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을 출력해야 한다)

예제 입력 1 
3
2 3 5
2
4 5
예제 출력 1 
10

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

const int MOD = 1e9;
typedef long long ll;

int N, M, a;
bool visited[40000];
vector <int> prime;
map <int, int> A, B;

void chk(int n, int b) {
	for (auto num : prime)
	{
		if (n % num==0 && b==0) {
			A[num]++;
			chk(n / num, 0);
			return;
		}
		else if (n % num==0 && b == 1) {
			B[num]++;
			chk(n / num, 1);
			return;
		}
	}
	if (n != 1 && b == 0) {
		A[n]++;
	}
	else if (n != 1 && b == 1) {
		B[n]++;
	}
}


int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	for (int  i = 2; i < 40000; i++)
	{
		if (!visited[i]) {
			prime.push_back(i);
			for (int j = 2; i*j < 40000; j++)
			{
				if (visited[i * j] == 0) {
					visited[i * j] = true;
				}
			}
		}
	}
	freopen("input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> a;
		chk(a,0);
	}
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> a;
		chk(a,1);
	}

	ll ans = 1;
	bool over = false;
	for (auto it : A) {
		int now = it.first;
		if (!B.count(now))	continue;
		int cnt = min(A[now], B[now]);
		while (cnt--) {
			ans *= now;
			if (ans > MOD) {
				over = true;
				ans %= MOD;
			}
		}
	}
	if (over) {
		ans %= MOD;
		cout.width(9);
		cout.fill('0');
		cout << ans << "\n";
	}
	else {
		cout << ans << "\n";
	}

	return 0;
}