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

問題

問題概要

省略

解法

Mが与えられ、その中で、同じ素因数であれば1回以上2回まで同時に割ることができる。よって、それぞれのMの中でさらに素因数ごとに山に分ける。そうすると、それぞれの山をmod3とった値がgrundy数となる。

mmxsrup.hatenablog.com

この問題と同じ感じだけど、一度にとれる枚数が限られるため、grundy数がすこし複雑になる。

ミス

grundy数理解したいね。使えるようにはなった気がする少しだけ。

コード

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


int main(void){
    int n; cin >> n;

    int sum = 0;
    rep(i, n){
        int m; cin >> m;
        for (int p = 2; p <= m; ++p){
            int cnt = 0;
            while(m % p == 0){
                cnt++;
                m /= p;
            }
            sum ^= cnt % 3;
        }
    }

    if(sum == 0){
        printf("Bob\n");
    }else{
        printf("Alice\n");
    }
    return 0;
}