UVa11859 Division Game
概要
プレイヤー二人が交互に対戦する。行列から行を選べるので、その行の要素それぞれについて1以外で割り切れる数の内好きな数で割って良い。一つも割り切れる要素がない場合(つまり行の要素が全て1の場合)その行は選ぶことは出来ない。自分の番のときに行列が全て1であったら負けとなる。
解法
まず行列の値をその数の素因数の数に変換する。
選んだ行の各要素を好きな数字で割れるので、行の要素をひとまとめにして列のみの Nim と見ることができる。
#include <iostream> #include <algorithm> using namespace std; int prime_factor(int x) { int ret = 0; int const y = x; for(int i=2; i*i<=y; i++) { while(x % i == 0) { ret ++; x /= i; } } if(x > 1) ret ++; return ret; } int main() { int Tc; cin >> Tc; for(int Tcnt=1; Tcnt<=Tc; Tcnt++) { int H, W; cin >> H >> W; int nim = 0; for(int i=0; i<H; i++) { int sum = 0; for(int j=0; j<W; j++) { int in; cin >> in; sum += prime_factor(in); } nim ^= sum; } cout << "Case #" << Tcnt << ": " << (nim != 0 ? "YES" : "NO") << endl; } return 0; }