TopCoder SRM 575 Div1

역시 옐로는 아직 내가 있을 곳이 아니다 ㅋㅋㅋㅋㅋㅋㅋ

올라가자마자 블루로 po강등wer매치..

아아ㅏㅏㅏㅏ250게임따위를 틀리다니 멍청이ㅜㅜ

250

John과 Brus가 수를 가지고 게임을 합니다 (John이 먼저 시작).

각자의 차례에서 할 수 있는 행동은 현재의 수에서

현재 수의 약수중 1과 자기 자신이 아닌 약수 하나를 빼는것입니다.

만일 자신의 차례에서 소수를 만난다면 패배!.. ㅜㅜ 으앙..

두 명 모두 최선을 다해서 게임을 진행할 때, 승자를 맞춰보세요. (N은 10^18 이하의 자연수)

이 문제는 아직 정확한 이유는 잘 모르겠는데,

열~~~심히 생각하다보니까.. 주어지는 수가 홀수면 무조건 Brus가 이기고,

짝수일 경우에는 주어진 수가 4의 배수이거나 (이걸 빼먹었다..ㅜㅜ)

주어진 수를 소인수분해해서 나오는 소인수로 주어진 수를 나눈 몫과

소인수의 parity가 다른 경우가 있을 경우 John이 이기고, 나머지는 Brus가 이긴다.

으아ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ아악 ㅜㅜ

500

1000