백준 7501번: Key

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

7501번: Key

---

케이스 분류를 차근차근 해보면 쉽게 접근할 수 있는 문제입니다.

---

Case 1 : K가 소수일 때

Wilson's Theorem에 따르면,

$$(p-1)! \equiv -1 \;\; (\textrm{mod} \; p)$$

입니다. $(p-1)!$이 $p$의 배수가 아니므로 $p^{2}$으로 divisible 할 수가 없습니다.

 

따라서, $K \in \mathbb{P}$ 이면 반드시 문제에서 말하는 key에 해당합니다. 단, K가 2인 경우는 제외해야 하는데, 사실 입력되는 범위부터 2는 배제되어 있습니다.

 

다른 방법으로, $(p-1)!$ 의 소인수분해에서 $p$가 한 번도 등장하지 않는 것을 눈치챌 수도 있고, 이 방법이 다른 케이스에서 효과적으로 사용됩니다.

---

Case 2 : K의 소인수분해가 $p^{e}$ 일 때

Legendre's Formula 에 따르면, $n!$ 의 소인수분해에서 소수 $p$ 의 등장 횟수는

$$v_{p} (n!) = \sum_{i=1}^{\infty} \lfloor \frac{n}{p^{i}} \rfloor$$

입니다. 이를 활용할 수 있게 문제를 조금 변형하겠습니다.

 

$(p^{e})!$ 가 $p^{3e}$ 로 divisible하지 않은 경우가 존재하는가?

 

변형한 문제가 원래 문제와 같음을 쉽게 알 수 있습니다. 변형 문제에 대해 Legendre's Formula 를 적용하면

$$v_{p} (p^{e}!) = \frac{p^{e} - 1}{p-1}$$

이제 변형 문제의 답은

 

소수 $p$ 와 $e \geq 2$ 에 대해 $\frac{p^{e} - 1}{p-1} < 3e$ 를 만족하는 경우가 존재하는가?

 

의 답이며, 식을 풀어보면

$$p = 2, e = 2, 3$$

$$p = 3, e = 2$$

뿐임을 얻을 수 있습니다. 한편, 원래 문제는 key가 반드시 홀수여야 한다고 했으므로, 이 케이스에서 $K=9$ 만이 valid 합니다.

---

Case 3 : K가 소인수가 2개 이상인 홀수 합성수일 때

$K$ 의 소인수분해를 다음과 같이 가정합니다.

$$K = p_{1}^{e_{1}} \times p_{2}^{e_{2}} \times \cdots \times p_{d}^{e_{d}}$$

이때 Legendre's Formula 에 의해

$$v_{p_{i}} (K-1)! \geq \lfloor \frac{K - 1}{p_{i}} \rfloor = \frac{K}{p_{i}} - 1 \geq 2 \;\; (1 \leq i \leq d)$$

따라서 이러한 $K$ 는 반드시 key일 수 없습니다.

---

Appendix : K가 소인수가 2개 이상인 짝수 합성수일 때

문제에서는 필요없지만, 증명의 완결을 위한 마지막 케이스입니다. $K$ 의 소인수분해를 다음과 같이 가정합니다.

$$K = 2^{x} \times p_{1}^{e_{1}} \times \cdots \times p_{d}^{e_{d}}$$

(1) d = 1, x = 1

$K = 2p$ 로 놓으면, $(2p-1)!$ 을 전개했을 때 $p$ 의 배수는 $p$ 가 유일합니다. 따라서 $K = 2p$ 는 key에 해당합니다. ($p \geq 3$)

 

그러면, $e \geq 2$ 에 대해 $K = 2p^{e}$ 이면 어떨까요? (단, $e \geq 2$)

$$v_{p} ((2p^{e} - 1)!) = \sum_{i=1}^{\infty} \lfloor \frac{2p^{e} - 1}{p^{i}} \rfloor = 2(p^{e-1} + p^{e-2} + \cdots + p^{0}) - p$$

이로부터 $K = 2p^{e}$ 가 key에 해당할 조건은

$$p^{e} - 1 < \frac{p - 1}{2} \times (p + 2e)$$

입니다만, 어떤 $p,e$ 도 이를 만족하지 않습니다. 즉, $K = 2p^{e}$ 는 key에 해당하지 않습니다.

(2) d = 1, x > 1

먼저, $K = 2^{x}p$ 로 놓고 Legendre's Formula 를 사용합니다.

$$v_{2} ((2^{x}p - 1)!) \leq p(2^{x-1} + \cdots + 2^{0}) - p = p(2^{x} - 2)$$

이므로 key일 조건은

$$p < \frac{x}{2^{x-1} - 1}$$

입니다. 하지만, $x > 1$ 이므로 위 부등식을 만족하는 소수 $p$ 는 없습니다.

 

따라서, $K = 2^{x}p$ 또는 $K = 2p^{e}$ 가 모두 key 가 될 수 없으며

 

다른 말로는 $d=1$ 에서 $K = 2p$ 를 제외하면 key가 없습니다.

(3) otherwise

같은 아이디어로 증명할 수 있습니다. 결론은, 이러한 $K$ 는 key에 해당하지 않습니다.

---

이상으로부터 결론을 내릴 수 있습니다.

 

$K = p$ 또는 $K = 2p$ 또는 $K = 4, 8, 9$ 일 때만이 $K^{2} \nmid (K-1)!$ 을 만족한다.

 

하지만, 문제에서 원하는 건 홀수 key 이므로, 결국 문제는 주어진 범위에서 소수 판정을 효율적으로 하는 방법을 묻는 것입니다.

 

주어지는 범위가 최대 $10^{18}$ 이므로, deterministic 한 Miller-Rabin Test 를 통해 소수 판정을 진행합니다.

 

아래는 제 코드입니다.

#include <iostream>
#include <vector>

namespace Primality {
	using u32 = unsigned int;
	using u64 = unsigned long long;
	
	bool sqrt_test (u64 N) {
		/* input value : N is odd and small 
		 * return value : {false := composite; true := prime}
		 * time complexity : sqrt(N)
		 * restriction : N < 10^9
		 */
		for (u32 i = 3; i * i <= N; i += 2) {
			if (N % i == 0) return false;
		}
		return true;
	}
	
	u64 power_modular (u64 X, u64 Y, u64 M) {
		u64 result = 1;
		while (Y) {
			if (Y % 2) {
				result = result * X % M;
			}
			X = X * X % M;
			Y /= 2;
		}
		return result;
	}
	
	using i128 = __int128;
	u64 power_modular_safe (u64 X, u64 Y, u64 M) {
		u64 result = 1;
		while (Y) {
			if (Y % 2) {
				result = (i128)result * X % M;
			}
			X = (i128)X * X % M;
			Y /= 2;
		}
		return result;
	}
	
	bool Miller_Rabin_Internal (u64 N, u64 K) {
		/* input value : N is odd, K < N
		 * return value : {false := composite; true := probable-prime}
		 *
		 * explanation :
		 * calculate k^d, k^(2d), k^(4d), ... , k^(2^s-1 * d)
		 * where 2^s * d = N - 1
		 * 
		 * Then, N is probably prime if k^d = +1/-1 or k^(2^k * d) = -1 mod N
		 * 
		 * time complexity : O(log^2 N)
		 */
		u64 d = N - 1;
		for (; d % 2 == 0; d /= 2) {
			if (power_modular_safe(K, d, N) == N - 1) {
				return true;
			}
		}
		if (u64 temp = power_modular_safe(K, d, N); temp == 1 || temp == N - 1) {
			return true;
		}
		else {
			return false;
		}
	}
	
	bool Miller_Rabin_test (u64 N) {
		/* input value : N is odd and large
		 * return value : {false := composite; true := prime}
		 *
		 * explanation :
		 * Originally, Miller_Rabin_Test can be wrong by 4^-k where k is number of rounds
		 * But, for small N, there is a deterministic way which has 100% accuracy
		 *
		 * time complexity : O(k log^2 N)
		 */
		std::vector<u64> list = {2, 7, 61};
		if (N > ((u64)1 << 32)) list =  {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
		
		for (auto i : list) {
			if (N % i == 0) return false;
			if (!Miller_Rabin_Internal(N, i)) return false;
		}
		return true;
	}
	
	bool is_Prime (u64 N) {
		if (N < 2) return false;
		if (N == 2 || N == 3) return true;
		if (N % 6 != 1 && N % 6 != 5) return false;
		if (N <= 1e4) return sqrt_test(N);
		return Miller_Rabin_test(N);
	}
}

using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	long long A, B;
	cin >> A >> B;
	
	for (long long i = A; i <= B; i++) {
		if (Primality::is_Prime(i) || i == 9) {
			cout << i << ' ';
		}
	}
	
	return 0;
}

(C++20, 0ms, 2024KB, 제출번호 67726620)

---