[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^a{q}^b$ $(ab>1)$라면?

koosaga가 $p^a{q}^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}\dots 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