[BOJ 24292 // C++] РАЗДЕЛЯЙ и ВЛАДЕЙ

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

 

이번에 볼 문제는 백준 24292번 문제인 РАЗДЕЛЯЙ и ВЛАДЕЙ이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/probelm/24292 

 

주어진 연산으로 $a$와 $b$는 곱이 $ab$와 같은 두 양의 정수로 바꿀 수 있다. 이 때 어떤 수 $g$가 $a$의 약수이면서 동시에 $b$의 약수가 되려면 $g^2$는$ab$의 약수여야 함을 관찰하자.

따라서 이 문제는 $ab$의 가장 큰 제곱수 인수를 구하는 문제가 된다. $a$와 $b$는 각각 2000000 이하이므로 두 수를 각각 소인수분해하여 $ab$의 가장 큰 제곱수 인수를 구하자.

각 수의 약수인 소수를 저장해놓은 배열은 에라토스테네스의 체를 만드는 것과 같은 방식으로 얻을 수 있으며, 이 배열을 미리 전처리해둘 경우 각 정수 $n$의 소인수분해를 $O(\lg n)$에 해낼 수 있다. 이를 이용해 소인수분해를 빠르게 해내자.

 

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

#include <iostream>
#include <algorithm>
using namespace std;

int sieve[2000001];
void sieveinit() {
	sieve[1] = 1;
	for (int i = 2; i < 2000001; i++) {
		if (sieve[i]) continue;
		for (int j = i; j < 2000001; j += i) sieve[j] = i;
	}
}
int N, Q;

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

	sieveinit();
	cin >> N >> Q;
	while (Q--) {
		vector<int> vec;
		int A, B; cin >> A >> B;
		while (A > 1) {
			vec.emplace_back(sieve[A]);
			A /= sieve[A];
		}
		while (B > 1) {
			vec.emplace_back(sieve[B]);
			B /= sieve[B];
		}
		sort(vec.begin(), vec.end());
		int old = 1, ans = 1;
		for (auto &x:vec) {
			if (old == x) {
				ans *= x;
				old = 1;
			}
			else old = x;
		}
		cout << ans << ' ';
	}
}