백준 2824번 최대공약수

<백준 2824번 최대공약수 - 마포 코딩박>

사용한 알고리즘: 에라토스테네스의 체


문제에서 N개 수의 곱 A 와 M개 수의 곱 B 의 gcd 를 묻고 있습니다.

문제풀이는 다음과 같습니다.

(1) 수는 최대 10^9이 주어지므로 에라토스테스의 체로 40000까지의 소수들을 구해줍니다. ( 어떤 수 A 는 root(A) 이상의 소수로는 나눠지지 않습니다. )

(2) map을 사용하여 N개의 수가 입력될 때 각 수들의 소인수 분해 값을 저장합니다. M개의 수가 입력될 때 이를 반복합니다. (단, 따로 저장)

(3) 구하고자 하는 값을 ans (long long)로 놓고, A의 수에대해 저장한 소인수 분해 값들을 보면서, B의 수에 대한 소인수 분해와 겹치는 만큼 ans에 곱해줍니다.

(4) 과정 (3)을 할 때, ans 가 10^9이 넘어가는지 체크해주고, 넘어간다면 이를 10^9으로 modulo 취해줍니다.

(5) 과정 (4)에서 10^9이 넘어간다고 체크된 경우 출력시 9자리까지만 출력하라는 조건에 유의해서 출력합니다. 제 경우에는 width 함수를 사용하였고, 남는 자리는 fill 함수로 0을 채워줬습니다.

	#include <bits/stdc++.h>
	using namespace std;
	#define ll long long
	const int MOD = 1000000000;
	// 문제에서 요구하는 출력형식을 맞춰주고, 답이 너무 커져 터지는걸 유의.
	int N, M;
	map<int, int> A, B;
	vector<int> Prime;
	bool visited[40000];
	void MakeA(int a){
	for(auto now: Prime){
	if(a%now==0){
	A[now]++;
	MakeA(a/now);
	return;
	}
	}
	if(a!=1) A[a]++;
	}
	void MakeB(int a){
	for(auto now: Prime){
	if(a%now==0){
	B[now]++;
	MakeB(a/now);
	return;
	}
	}
	if(a!=1) B[a]++;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	for (int i = 2; i < 40000; ++i){
	if(visited[i]) continue;
	Prime.push_back(i);
	for (int j = 2*i; j < 40000; j+=i) visited[j] = true;
	}
	bool Over = false;
	cin >> N;
	for (int i = 0; i < N; ++i){
	int num;
	cin >> num;
	MakeA(num);
	}
	cin >> M;
	for (int i = 0; i < M; ++i){
	int num;
	cin >> num;
	MakeB(num);
	}
	ll ans = 1LL;
	for(auto iter: A){
	int now = iter.first;
	if(!B.count(now)) continue;
	int cnt = min(A[now],B[now]);
	while(cnt--){
	ans*=now;
	// ans 가 MOD 보다 큰값인지 아닌지 체크! (출력형식이 달라짐)
	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;
	}

view raw BOJ 2824.cpp hosted with ❤ by GitHub