yukicoder : No.2725 Coprime Game 2

なるほど。
https://yukicoder.me/problems/no/2725

問題

正整数をとる変数yを用いて、2人対戦のターン制ゲームを行う。
yの初期値をNとする。
各自のターンでは以下を行う。

• 2以上y以下の整数xのうち、Nの約数ではなく、yと互いに素であるものを選び、y=xで上書きする。
• そのようなxを選べなかったら負け。

Nが与えられたとき、先手後手どちらが必勝か答えよ。

解法

Nが2の場合は自明なので、それ以外の場合を考える。
Nと互いに素な最小の素数pを考える。
初手でpを取れれば、後手は次を選べないので先手必勝。
pを取れない場合、初手がp以外を取ると後手がpを取れるので後手必勝。

int T;
ll N;

const int prime_max = 55;
vector<int> prime;
int NP,divp[prime_max];

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime.push_back(i); NP++;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	cin>>T;
	while(T--) {
		int tp=0;
		cin>>N;
		FORR(p,prime) {
			if(N%p) {
				tp=p;
				break;
			}
		}
		for(i=1;i<tp;i++) if(N%i) break;
		if(i==tp&&N>2) {
			cout<<"K"<<endl;
		}
		else {
			cout<<"P"<<endl;
		}
		
	}
}

まとめ

コードは短いね。