백준 14860 / C++

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

14860번: GCD 곱

 

[ 풀이 ] 

어려운 문제였다. 각 소인수마다 최대지수를 구해주면 되는데 구하는 과정이 어렵다.

2의 최대지수를 구해보자. 2의 최대지수를 구할 때 n/2 * m/2 가 짝수인 쌍의 개수이다. 

이때, 4의 최대지수를 구할 땐 2의 최대지수를 구하는 과정에서 값이 1번 세졌다는 사실을 이용한다. 

4=2^2이고 2에서 1이 세졌으므로 1번만 세주면 된다. 즉 그냥 n/4*m/4를 더해주면 된다. 

따라서 2의 최대지수는 sum((n/2^i)*(m/2^i))가 된다. min(m,n)이하 모든 소수들에 대해 이걸 해주면 된다.

매번 거듭제곱씩 증가하므로 시간복잡도 O(NKlogK)에 해줄 수 있다. (K=min(m,n))

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 15000005;
ll n, m, p[MAX];
const ll MOD = 1e9 + 7;

void make_prime(ll N) {
	p[2] = 1;
	for (ll i = 3; i <= N; i += 2) p[i] = 1;
	for (ll i = 3; i <= N; i += 2) {
		if (!p[i]) continue;
		for (ll j = i; i * j <= N; j += 2) {
			p[i * j] = 0;
		}
	}
}

ll Pow(ll a, ll b) {
	ll ret = 1;
	while (b) {
		if (b & 1) ret = (ret * a) % MOD;
		a = (a * a) % MOD;
		b >>= 1;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	ll k = min(m, n);
	make_prime(k);
	ll ans = 1;
	for (ll i = 2; i <= k; i++) {
		if (!p[i])continue;
		ll cnt = 0;
		for (ll j = i; j <= k; j *= i) {
			cnt += (n / j) * (m / j);
		}
		ans *= Pow(i, cnt);
		ans %= MOD;
	}
	cout << ans;
}