【UVA11859】Division Game（SG函数，Nim游戏）

题意：给定一个n*m的矩阵，两个游戏者轮流操作。

每次可以选一行中的1个或多个大于1的整数，把它们中的每个数都变成它的某个真因子，不能操作的输。

问先手能否获胜

n,m<=50,2<=a[i][j]<=10000

思路：考虑每个数包含的质因子个数，则让一个数“变成它的真因子”等价于拿掉它的一个或多个质因子。

这样，每行对应一个火柴堆，每个数的每个质因子看成一根火柴，则本题就和Nim游戏就完全等价了。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 typedef long long ll;
 7 using namespace std;
 8 #define N   110
 9 #define oo  10000000
10 #define MOD 1000000007
11 
12 int sg[N];
13 
14 int main()
15 {
16     int cas;
17     scanf("%d",&cas);
18     for(int v=1;v<=cas;v++)
19     {
20         int n,m;
21         scanf("%d%d",&n,&m);
22         for(int i=1;i<=n;i++)
23         {
24             sg[i]=0;
25             for(int j=1;j<=m;j++)
26             {
27                 int x;
28                 scanf("%d",&x);
29                 int y=x;
30                 for(int k=2;k*k<=y&&x>1;k++)
31                 {
32                     while(x>1&&x%k==0)
33                     {
34                         sg[i]++;
35                         x/=k;
36                     }
37                 }
38                 if(x>1) sg[i]++;
39             }
40         }
41         int ans=0;
42         //for(int i=1;i<=n;i++) printf("%d %d
",i,sg[i]);
43         for(int i=1;i<=n;i++) ans^=sg[i];
44         if(ans!=0) printf("Case #%d: YES
",v);
45          else printf("Case #%d: NO
",v);
46     }
47     return 0;
48 }
49