백준 3752번: 최대공약수 행렬식

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

3752번: 최대공약수 행렬식

---

수학적으로는 어렵지만 코딩은 쉬운 문제입니다.

 

Zhongshan Li의 1990년 paper 을 보면, 3752번에서 쓰는 모든 표현이 그대로 나오고 있습니다. 즉

$$\textrm{det} [S] = \prod_{x \in S} \phi (x)$$

이것을 그대로 구현하면 정답을 받습니다.

 

Totient Function의 구현에 대하여, 문제에서 $x < 2 \times 10^{9}$이므로 소인수분해 기반 $O(\sqrt{x})$ 구현이 충분히 통과하고, 다만 범위가 충분히 작기 때문에 constant factor에 의하여 Pollard-Rho 기반 구현은 상대적으로 느릴 수 있습니다. Totient function의 정의 중 하나를 쓰면

$$\phi (x) = x \times \prod_{p | x} \left ( 1 - \frac{1}{p} \right )$$

주어진 범위에 의해 Eratosthenes' Sieve로 prime factors를 빠르게 얻을 수 있고 totient function도 빠르게 구해집니다.

 

저는 $O(\sqrt{x})$ 구현을 썼습니다.

#include <stdio.h>
#define mod 1000000007

long long PHI (long long x);

int main() {
	
	int T;
	scanf("%d", &T);
	while(T--) {
		int n;
		scanf("%d", &n);
		
		long long answer = 1;
		while(n--) {
			long long temp;
			scanf("%lld", &temp);
			answer = answer * PHI(temp) % mod;
		}
		printf("%lld\n", answer);
	}
	return 0;
}

long long PHI (long long x) {
	long long result = x;
	if (x % 2 == 0) {
		while (x % 2 == 0) {
			x /= 2;
		}
		result -= result / 2;
	}
	for (long long i = 3; i * i <= x; i += 2) {
		if (x % i == 0) {
			while (x % i == 0) {
				x /= i;
			}
			result -= result / i;
		}
	}
	if (x > 1) {
		result -= result / x;
	}
	return result;
}​

(C11, 48ms, 1116KB, 제출번호 55721319)

---

Sieve를 쓰는 경우 대략 12ms까지 줄일 수 있었습니다. (제출번호 55723997) $\sqrt{2 \times 10^{9}} < 50000$ 임을 이용하면 sieve를 통해 그 이하의 prime만 구해도 충분함을 알 수 있습니다.