题目:题目链接
题意:题目意思很明确。就是现在有N个数字,每次一个人上去,可以把一个数字换成它的一个因子替换。直到有一
个人使得所有的数字的乘积为1的时候,这个人就赢了。
分析:因为我们知道:对于任意一个数字A,我们都可以把这个数字写成A=p1^q1 * p2^q2 * ……* pn^qn (pi是质
数)、所以我们每次的操作就相当于任选一个数字。然后从中拿走若干素数。这样的话,问题就可这个数字中存在的
素数的个数有关了。这样就回归到了Nim博弈,相当于有n堆石子,每次选一堆,从中拿走一部分石子,问最后谁赢,
所以,我们只要处理每一个数字的素数因子的个数就可以了(不过,估计写挫了,跑了3620ms)
代码:
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int QuickMod(int a,int b,int n) { int r = 1; while(b) { if(b&1) r = (r*a)%n; a = (a*a)%n; b >>= 1; } return r; } #define maxn 100010 int num[maxn]; int cnt[maxn]; int prime[3000]; bool isprime(int x) { if(x == 0 || x == 1)return false; if(x == 2 || x == 3)return true; for(int i = 2; i*i <= x; ++i) if(x%i == 0)return false ; return true; } int T; int n; void init() { int k = 0; for(int i = 0; i < 2500; ++i) { if(isprime(i)) prime[k++] = i; } T = 0; } int work(int &x) { int ans = 0; for(int i = 0; prime[i]*prime[i] <= x; ++i) { while(x % prime[i] == 0) { x /= prime[i]; ans++; } } if(x != 1) ans++; return ans; } void solve() { int ans = 0; T++; for(int i = 0; i < n; ++i) { cnt [i] = work(num[i]); ans ^= cnt[i]; } if(!ans)printf("Test #%d: Bob\n",T); else { for(int i = 0; i < n; ++i) { int flag = 0; int tp = ans ^ cnt[i]; if(!flag) { for(int j = 0; j < cnt[i]; ++j) { if((tp^j) == 0) { flag = 1; break; } } } if(flag) { printf("Test #%d: Alice %d\n",T, i+1); break; } } } } int main() { init(); while(scanf("%d", &n) == 1) { mem(num, 0); mem(cnt, 0); for(int i = 0; i < n; ++i) scanf("%d", &num[i]); solve(); } return 0; }