読者です 読者をやめる 読者になる 読者になる

h_nosonの日記

競プロなど

yukicoder No.103 素因数ゲーム リターンズ

問題
No.103 素因数ゲーム リターンズ - yukicoder
N個の整数M_1,M_2,...,M_Nが与えられる.
一度の操作で任意の整数M_iをその素因数で割ることができる.同じ素因数ならば2回まで同時に割れる.
AliceとBobが交互に操作を行うとき,すべての整数を1にできるのはどちらか.

解法
M_igrundy数を求める.0を負けの状態,1,2を勝ちの状態とすると
1=(状態0),2=(状態1),2^2=(状態2),2^3=(状態0),2^4=(状態1),...
としてルールに従うと,(状態0)から(状態0)にすることはできず,(状態1),(状態2)からは(状態0)にすることができるということが分かる.つまり,指数部\bmod3を状態にすればよくなる.
M_i=\prod p_j^{a_j}と表すとき,grundy数はすべての a_j\bmod3排他的論理和となる.後はすべてのM_igrundy数について排他的論理和をとれば勝敗がわかる.

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP (i,0,(int)(n)-1)
#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP (i,(int)(n)-1,0)
#define INF (int)1e8
#define MOD (int)(1e9+7)

typedef long long ll;

int main(void) {
    int i, j, n;
    int m[100], grundy[100];
    cin >> n;
    rep (i,n) cin >> m[i];
    rep (i,n) {
        map<int,int> mp;
        int x = m[i];
        for (j = 2; j * j <= x; j++) {
            if (x % j == 0) {
                mp[j]++;
                x /= j;
                j--;
            }
        }
        mp[x]++;
        grundy[i] = 0;
        for (auto p : mp)
            grundy[i] ^= p.second % 3;
    }
    int ans = 0;
    rep (i,n) ans ^= grundy[i];
    if (ans == 0)
        cout << "Bob" << endl;
    else
        cout << "Alice" << endl;
    return 0;
}