[Baekjoon - 16894] 약수 게임

난이도: Gold III

 

태그

• Game Theory
• Number Theory → Prime Factorization

 

풀이

1. \( N = 1 \)이라면?

아무 행동도 할 수 없으니, 정의상 koosaga가 승리합니다.

 

2-1. 어떤 소수 \( p \)에 대해, \( N = p \)라면?

\( p \)를 지운 뒤 아무것도 할 수 없으니, koosaga가 승리합니다.

 

2-2. \( N = p^2 \)이라면?

koosaga는 \( p^2 \)을 \( p \)로 바꿀 수 밖에 없고, 이후는 [2-1]에 의해 cubelover가 승리합니다.

 

2-3. \( N = p^3 \)이라면?

koosaga가 \( p^3 \)을 \( p^2 \)으로 바꾸면, [2-2]에 의해 koosaga가 승리합니다.

 

2-4. 일반화해서, \( N = p^k \) \( (k \ge 3) \)이라면?

koosaga가 \( p^k \)을 \( p^2 \)으로 바꾸면, [2-2]에 의해 koosaga가 승리합니다.

 

3-1. \( N = pq \)라면?

koosaga가 둘 중 하나의 소수만 남겨야 하므로, \( pq \)가 \( p \)로 변하게 됩니다.

이후는 [2-1]에 의해 cubelover가 승리합니다.

 

3-2. 그럼, \( N = p^aq^b \) \( (ab > 1) \)라면?

koosaga가 \( p^aq^b \)를 \( pq \)로 바꿀 수 있으므로, [3-1]에 의해 koosaga가 승리합니다.

 

4-1. \( N = pqr \)이라면?

koosaga가 \( pqr \)을 \( pq \)로 바꿀 수 있으므로, [3-1]에 의해 koosaga가 승리합니다.

 

4-2. \( N = p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k} \) \( (k \ge 3) \)라면?

소수가 많다고 겁먹지 마세요. koosaga가 위 수를 \( p_1 p_2 \)로 바꿀 수 있으므로 [3-1]에 의해 koosaga가 승리합니다.

 

5. 결론을 요약하면?

koosaga가 패배하는 경우는 \( N = p^2 \)이거나 \( N = pq \)인 경우밖에 없습니다.

그러므로, \( N \)을 소인수분해한 뒤 두 소수의 곱으로 이루어져있는지 판별하면 됩니다.

 

6. 코드

https://carbon.now.sh