UVa11859 Division Game

概要
プレイヤー二人が交互に対戦する。行列から行を選べるので、その行の要素それぞれについて１以外で割り切れる数の内好きな数で割って良い。一つも割り切れる要素がない場合（つまり行の要素が全て１の場合）その行は選ぶことは出来ない。自分の番のときに行列が全て１であったら負けとなる。

解法
まず行列の値をその数の素因数の数に変換する。
選んだ行の各要素を好きな数字で割れるので、行の要素をひとまとめにして列のみの 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;
}