yukicoder No.2 素因数ゲーム

問題

問題概要

複数山の石取りゲーム

解法

まず、素因数分解をします。そして、同じ素因数の数を数える。素因数の因数のどおしをxorで計算する。すべての素因数に対してその処理を行い、その結果が0であれば、後攻の人がかつ。この問題は必勝法が存在するのでこのようなことができます。 参考サイト二ムゲームといわれるものらしいです。参考サイトがとてもわかりやすい。

ミス

初めて知った。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(void){
    ll n; cin >> n;
    int ans = 0;
    for (int i = 2; i <= n; ++i){
        int cnt = 0;
        while(n % i == 0){
            cnt++;
            n /= i;
        }
        ans ^= cnt;
    }
    //ans=0ははじめの状態で必勝形なので、後攻の人が勝てる
    if(ans == 0) printf("Bob\n");
    else printf("Alice\n");
    return 0;
}