UVA 11859 - Division Game

题意：给定一个矩阵。每次能选一行中几个数字，把他们变成他们的因子，最后不能变的人输。问能否先手必胜

思路：转变成因子等价于删去一些素数。这样问题转化为了Nim游戏

代码：

#include 
     
      #include 
      
       const int N = 10005;int t, n, m, num, cnt[N], vis[N], prime[N], pn = 0;int main() {	for (int i = 2; i < N; i++) {		if (vis[i]) continue;		prime[pn++] = i;		for (int j = i; j < N; j += i) {			vis[j] = 1;  		} 	} 	for (int i = 2; i < N; i++) { 		int num = i;   		for (int j = 0; j < pn && prime[j] <= i; j++) { 			while (num % prime[j] == 0) { 				cnt[i]++; 				num /= prime[j]; 			}   		}  	} 	int cas = 0;	scanf("%d", &t);	while (t--) {		int ans = 0;		scanf("%d%d", &n, &m);		for (int i = 0; i < n; i++) {			int sum = 0;   			for (int j = 0; j < m; j++) {   				scanf("%d", &num);				sum += cnt[num];   			}   			ans ^= sum;  		}  		printf("Case #%d: %s\n", ++cas, ans == 0?"NO":"YES"); 	}	return 0;}
      
     

版权声明：本文博客原创文章，博客，未经同意，不得转载。