[BOJ 14860 // C++] GCD 곱

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

 

이번에 볼 문제는 백준 14860번 문제인 GCD 곱이다.
문제는 아래 링크를 확인하자.

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

14860번: GCD 곱

모든 수의 쌍에 대하여 gcd를 구한다면 시간초과가 날 것이다.

대신, gcd를 구성하는 수를 소인수별로 구해서 그 개수를 한번에 binary exponentiation으로 곱해주면 빠르게 계산할 수 있다.

 

소수를 구할 때 i*i가 32비트 정수 범위를 넘어설 수 있음에 유의하자.

 

어디서 Clang의 단순 연산 반복문의 최적화 성능이 좋다는 말을 주워들어서 gcc와 clang 모두 제출해보았더니 이 문제에 대한 글쓴이의 코드는 clang이 더 빠르게 채점이 된다는 사실을 알 수 있었다.

 

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

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

vector<bool> sieve(15000001);
vector<ll> primes;

ll ans = 1;

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

	int N, M; cin >> N >> M;
	int x = min(N, M);
	for (ll i = 2; i <= x; i++) {
		if (sieve[i]) continue;
		primes.push_back(i);
		for (ll j = i * i; j <= x; j += i) sieve[j] = 1;
	}
	for (auto p : primes) {
		ll pp = p;
		ll cnt = 0;
		while (pp <= x) {
			cnt += (N / pp) * (M / pp);
			pp *= p;
		}
		while (cnt > 0) {
			if (cnt & 1) {
				ans *= p;
				ans %= 1000000007;
			}
			cnt >>= 1;
			p *= p;
			p %= 1000000007;
		}
	}

	cout << ans;
}