[백준] 16894: 약수게임

문제 링크

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

접근 방식 / 풀이

더 이상 적을 수가 없는 사람이 이기는 게임이고, 구사과가 먼저 게임을 진행한다.
모든 사람은 자신이 유리하도록, 최선으로 게임을 플레이한다.

큐브러버가 이기기 위해서는, 구사과가 적는 수가 소수여야 한다.
즉, 맨 처음 주어지는 수는 소수 2개의 곱으로 이루어져야 한다.

이 경우를 제외한 모든 경우에는 구사과가 이긴다.
(주어지는 수가 소수거나, 1이거나, 소수 2개의 곱이 아닌 수)

따라서 이를 판별해주어야 하는데, 큐브러버가 이기는 경우만 판단해주면 된다.
입력이 $10^{13}$이기 때문에 전체를 다 도는 것은 무리라고 판단했다.

$n$을 나눴을 때 나누어 떨어지는 $2 <= i <= sqrt(n)$ 인 $i$가 존재한다면, $sqrt(n) <= j < n$ 인 $j$ 또한 존재하기 때문에 소수판별을 하듯이 sqrt(n)까지만 진행해주면 이 수가 어떤 수의 곱으로 이루어져있는 지 알 수 있다.

결론적으로, 큐브러버가 이길 수 있는 경우는, $2 <= i <= sqrt(n)$ 의 범위 내에 $i$ 가 하나만 존재하는 경우이기에 이 경우만 찾아주고, 나머지는 구사과가 이기는 경우로 판단하면 된다.

• 주의해야 할 점
  $8$과 같이 어떤 수의 세제곱꼴인 경우를 찾게 되면, $\sqrt{8}$ 은 4보다 작기에 소수가 $2$ 단 하나로 판별되기 때문에 소수 두 개의 곱인 경우라고 판단할 수 있으나, 실은 그렇지 않기에, 나눠지는 $i$가 있다면 해당 수로 판별을 다시 진행하며 같은 소수가 여러 개 있는 경우도 고려해야 한다.

---

답안 코드 링크 (Github)

Github Solution Link

정답 코드 (C++)

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
int div_num;
long long  n;

int main(void)
{
	cin >> n;
	for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {    
            div_num++;
            if (div_num > 1)
                break ;
            n /= i;
            i--;
        }
    }
	if (div_num == 1)
	    cout << "cubelover\n";
	else
	    cout << "koosaga\n";
	return (0);
}