백준 14860번: GCD 곱

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

14860번: GCD 곱

---

$GCD\left ( 1,1 \right)\times \cdots \times GCD\left ( N,M \right)$ 을 구하는 문제입니다.

 

$N\;,\;M$ 의 범위를 살펴보니, 위 식을 소인수분해하는 게 가능할 것 같습니다.

 

그러면 eratosthenes' sieve로 15000000 이하의 소수를 모두 구하고 나면,

 

각 소수가 몇 번 등장하는 지가 중요하겠네요.

 

$N=M=9$ 로 가정하고 $2$ 와 $3$ 의 등장 횟수를 살펴보겠습니다.

---

$\left( 1 \right)$ $2$ 의 등장 횟수

	1	2	3	4	5	6	7	8	9
1
2		1		1		1		1
3
4		1		1+1		1		1+1
5
6		1		1		1		1
7
8		1		1+1		1		1+1+1
9

첫번째 단계로, $GCD\left ( i,j \right)$ 에 2가 포함되는 곳에 '1' 을 씁니다.

 

두번째는, $GCD\left ( i,j \right)$ 에 4가 포함되는 곳에 "+1" 을 씁니다.

이미 첫번째 단계에서 2를 한 번 세고 지나간 곳이기 때문입니다.

 

세번째는, $GCD\left ( i,j \right)$ 에 8이 포함되는 곳에 "+1" 을 씁니다.

이미 첫번째, 두번째 단계에서 2를 두 번 세고 지나갔기 때문입니다.

 

더 이상의 단계를 진행해도 9까지의 숫자만 있는 위 표에서는 의미가 없습니다.

 

그렇다면, 2가 등장한 횟수는, 다음과 같겠군요.

 

$2$ 의 배수의 갯수 $+$ $2^{2}$ 의 배수의 갯수 $+$ $2^{3}$ 의 배수의 갯수

 

---

$\left( 2 \right)$ $3$ 의 등장 횟수

	1	2	3	4	5	6	7	8	9
1
2
3			1			1			1
4
5
6			1			1			1
7
8
9			1			1			1+1

첫번째 단계로, $GCD\left ( i,j \right)$ 에 3이 포함되는 곳에 '1' 을 씁니다.

 

두번째는, $GCD\left ( i,j \right)$ 에 9가 포함되는 곳에 "+1" 을 씁니다.

이미 첫번째 단계에서 3을 한 번 세고 지나간 곳이기 때문입니다.

 

더 이상의 단계를 진행해도 9까지의 숫자만 있는 위 표에서는 의미가 없습니다.

 

그렇다면, 3이 등장한 횟수는, 다음과 같겠군요.

 

$3$ 의 배수의 갯수 $+$ $3^{2}$ 의 배수의 갯수

 

 

---

이제 $N\times M$ 테이블로 확장합시다.

 

소수 $p$ 가 등장하는 횟수는 다음과 같을 것입니다.

 

$p$ 의 배수의 갯수 $+$ $p^{2}$ 의 배수의 갯수 $+$ $p^{3}$ 의 배수의 갯수 $+\cdots$

 

그런데 $p^{k}$ 가 등장하는 횟수는 분명히 다음과 같습니다.

 

$p^{k}$ 의 배수가 $N\times M$ 테이블에서 등장하는 횟수 : $\left \lfloor \frac{N}{p^{k}} \right \rfloor \times \left \lfloor \frac{M}{p^{k}} \right \rfloor$

 

따라서 우리는 다음을 구합니다.

 

$\sum_{k=1}\left \lfloor \frac{N}{p^{k}} \right \rfloor \times \left \lfloor \frac{M}{p^{k}} \right \rfloor$

 

이 값은 $GCD\left( 1,1 \right)\times GCD\left( N,M \right)$ 의 값에서 $p$ 가 곱해지는 횟수입니다.

 

그 횟수만큼 거듭제곱하는 것은 분할정복으로 해결하면 됩니다.

---

이제 sieve 를 활용하여 구현한 코드는 다음과 같습니다.

 

특별히 2의 배수만 먼저 처리한 것은 실행속도가 더 빨라지기 때문입니다.

#include <stdio.h>
#include <stdbool.h>
#define mod 1000000007

bool composite[15000001];

long long power_modular (long long x, long long y);

int main() {
	
	long long N, M;
	scanf("%lld %lld", &N, &M);
	long long min = (M > N) ? N : M;
	
	long long count = 0;
	for (int i = 2; i <= min; i *= 2) {
		count += ((N/i) * (M/i));
	}
	long long answer = power_modular (2, count);
	
	for (long long i = 3; i <= min; i += 2) {
		if (!composite[i]) {
			count = 0;
			for (long long j = i; j <= min; j *= i) {
				count += ((N/j) * (M/j));
			}
			answer = (answer * power_modular(i, count)) % mod;
			
			for (long long j = 3 * i; j <= min; j += 2 * i) {
				if (!composite[j]) {
					composite[j] = true;
				}
			}
		}
	}
	
	printf("%lld", answer % mod);
	return 0;
}

long long power_modular (long long x, long long y) {
	x %= mod;
	long long result = 1;
	while (y) {
		if (y % 2) {
			result = (result * x) % mod;
		}
		x = (x * x) % mod;
		y /= 2;
	}
	return result;
}

(C11, 15764KB, 128ms, 제출번호 26812591)

---

2의 배수를 먼저 처리하지 않아도 200ms 에 정답 처리됐습니다. (제출번호 26812126)