백준 16894번 약수 게임

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

16894번: 약수 게임

1 또는 소수가 주어지면 그 즉시 구사과가 이긴다.

주어진 수가 두 소수의 곱일때 그 수를 a * b(a, b는 소수)라 할 수 있고 이때 구사과는 수를 a 또는 b로 만들어야 하니 큐브러버가 이기게 된다.

위의 경우가 아닐 경우에는 주어진 수는 적어도 3개 이상의 소수의 곱이고 구사과가 두 소수의 곱으로 이루어진 수를 남겨 두번째 경우와 같은 이유로 이기게 된다.

따라서 주어진 수가 몇개의 소수의 곱으로 이루어져 있는지를 알면 답을 구해낼 수 있다.

 

#include<iostream>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie();
	cout.tie();
//count : 주어진 수를 이루는 소수의 갯수
	long long int N, count = 0;
	cin >> N;
	while (N && count <= 2){
		bool flag = false;
		for (long long int i = 2; i * i <= N; i++){
//N이 i로 나누어지면 break문이 동작하니 2 이상 i 미만인 자연수 중 N의 약수는 없고 i는 소수 입니다.
			if (!(N % i)){
				count++;
				N /= i;
				flag = true;
				break;
			}
		}
		if (N == 1) break;
//N ^ (1 / 2) 이하의 수들로 N이 나누어 떨어지지 않으면 N은 소수 입니다.
		else if (!flag){
			count++;
			break;
		}
	}

	if (count == 0 || count == 1 || count == 3) cout << "koosaga";
	else cout << "cubelover";

	return 0;
}