uva 11859 - Division Game(Nim)

题目链接：uva 11859 - Division Game

题目大意：给定一个N*M的矩阵，每次可以选择同一行中的若干个数，把它们变成它们的真因子。问说先手的可否胜利。

解题思路：将每一行中每个数的质因子看成是一个火柴，那么对于一行来说就是一个单堆的Nim游戏。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int div_factor (int n) {
    int ret = 0;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            ret++;
            n /= i;
        }
    }

    if (n > 1)
        ret++;
    return ret;
}

int main () {
    int cas, N, M;
    scanf("%d", &cas);
    for (int k = 1; k <= cas; k++) {
        int v = 0, x;
        scanf("%d%d", &N, &M);
        for (int i = 1; i <= N; i++) {
            int s = 0;
            for (int j = 1; j <= M; j++) {
                scanf("%d", &x);
                s += div_factor(x);
            }
            v ^= s;
        }
        printf("Case #%d: %s\n", k, v ? "YES" : "NO");
    }
    return 0;
}