BOJ 14860 GCD 곱

문제 링크입니다.

더블 카운팅

$\prod _{i=1} ^{N} \prod _{j=1} ^{M} \gcd (i, j)$를 구해야 합니다.

약수에 대한 합이나 곱 문제는 배수로 바꿔서 생각하면 쉬운 경우가 많습니다.

각 g마다 최대공약수가 g인 순서쌍의 개수를 구해 그만큼 거듭제곱해 주는 방식으로 문제를 풀어봅시다.

소인수마다 생각하기

g를 공약수로 갖는 순서쌍의 개수는 쉽게 구할 수 있지만, 최대공약수는 조금 다릅니다. 포함-배제의 원리를 이용해 다량의 계산으로 꾸역꾸역 각각 구하는 방법이 있겠지만, 좀 더 쉽게 풀어 봅시다.

g를 소인수분해하고, 각각의 소인수에 대해 문제를 풉시다. 각각의 소인수는 약수-배수 관계가 없어서 서로의 답에 영향을 주지 않습니다. 예를 들어 소인수 2에 대해 문제를 푸는 경우, 2 ^ (4의 배수가 아닌 2의 배수의 순서쌍 개수), 4 ^ (8의 배수가 아닌 4의 배수의 순서쌍 개수) … 를 구해 모두 곱하면 됩니다.

이것도 세는 방식을 바꿔서, 2 ^ (2의 배수의 순서쌍 개수), 2 ^ (4의 배수의 개수), …를 구해 모두 곱하는 것으로 같은 값을 얻을 수 있습니다.

결국 $\min(N, M)$ 이하의 모든 소수를 찾아두고, 각 소수마다 위의 작업을 반복하는 것으로 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod = 1e9+7;
bool isp[15151515]={1,1};
vector<ll> p;

ll pw(ll n, ll r){
	ll ret = 1;
	while(r){
		if(r&1) ret = ret*n%mod;
		n = n*n%mod;
		r >>= 1;
	}
	return ret;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	for(ll i = 2; i*i <= 15000000; i++){
		if(!isp[i]){
			for(ll j = i*i; j <= 15000000; j += i) isp[j] = 1;
		}
	}
	for(ll i = 2; i <= 15000000; i++) if(!isp[i]) p.push_back(i);
	ll n, m; cin >> n >> m;
	if(n > m) swap(n, m);
	ll ans = 1;
	for(auto i : p){
		if(i > n) break;
		ll now = i;
		while(now <= n){
			ans = ans*pw(i, (n/now)*(m/now))%mod;
			now *= i;
		}
	}
	cout << ans;
}