首页 > 代码库 > UVA 11859 - Division Game(Nim游戏)
UVA 11859 - Division Game(Nim游戏)
UVA 11859 - Division Game
题目链接
题意:给定一个矩阵,每次能选一行中几个数字,把他们变成他们的因子,最后不能变的人输,问是否能先手必胜
思路:转变成因子等价于删去一些素数,这样问题转化为了Nim游戏
代码:
#include <stdio.h> #include <string.h> 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。