yukicoder contest 2(No.2)解説

yukicoder

2020.11.23

若番は1つのコンテストに1つしか問題がないので記事が一杯書けますね＞＜

No.2 素因数ゲーム

No.2 素因数ゲーム - yukicoder

競技プログラミングの練習サイト

ある2以上の数Nが与えられる。
Nに対してある素因数aで好きなだけ割るということを二人で交互に行った場合、1を作れるプレイヤーはどちらか？

“素因数で好きなだけ割れる”を、各素因数の山があり、同じ山からは複数個取れる。
とした場合、あるゲームに似ている感じがします。

ニム - Wikipedia

競プロでおなじみnimです。
nimは最善手を取った場合、それぞれの山の数でXORを取った結果が0の場合、後攻が勝ちます、それ以外の場合は先手が勝ちます。

今回は山の数=素因数の数のため、素因数の数を調べてXORを取っていくことでどちらが勝つかを求めることができます。

#include<bits/stdc++.h>
//#include<atcoder/all>

using namespace std;
//using namespace atcoder;

int main(){
    int N;
    cin>>N;

    int r=sqrt(N)+2;
    int xr=0;

    for(int i=2;i<=r;i++){
        int c=0;
        while(N%i==0){
            c++;
            N/=i;
        }
        xr^=c;
    }
    if(N!=1) xr^=1;

    if(xr==0) cout<<"Bob"<<endl;
    else cout<<"Alice"<<endl;
}