题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4464
题目大意：给定n个数，每一步都可以将某个数替换为它的因子，但不能替换为本身，两个人轮流走，直到某个人走不了他就输了。问最后谁能赢，如果先手胜输出第一步。n<=10万，每个数<=5000000.
解题思路：数论+Nim。初看起来好像无从下手，但是细想：本题要找它的因子替换他自己，那么可以从这里入手。而每个数都可以表示成x = p1^a1*p2^a2...pk^ak，pi为质数，这样每个数都由(a1+a2+..ak)个质数组成，然后就转换成若干堆质数，每次可以取走某堆的某些个质数，问最后谁取无可取。
那不是传说中的裸Nim吗？把每堆的数量异或起来，结果为0为P态，先手负，结果非0，则先手胜，如果先手胜，必能与其中某个数异或后变成p态。若结果为ans，若每个数位a[i],则判断取走的那堆必须符合条件：temp = a[t] ^ ans,temp < a[t]，这样的话a[i] ^ a[j] ^...a[t] = ans可表示成a[i] ^ a[j] ^...temp ^ ans = ans, 也就是a[i] ^
a[j] ^... ^ temp = 0。
想A此题海必须解决一个问题，本题给的数似乎有点臃肿，怎么可以等于500万这么大？害我 TLE了好几次，最后无奈只能用个数组保存每个数最小的质因子，这样每次要确定p1^a1*p2^a2...pk^ak的ai总和时只要不断除以最小的因子直到出现不能除，n变成m，m又不断除以m的最小因子，这样反复直到值变为1.
接着就等着AC了。
测试数据：
4
111111 333333 4444444 5000000
10
1 2 3 4 5 6 7 8 9 10
4
111111 333333 4444444 5000000
5
1 3 5 7 9
4
1 3 5 7
4
1 3 5 5
4
5 5 5 5
5
5000000 5000000 5000000 5000000 1
5
5000000 4999999 4999999 4999999 4999998
3
1 2 4
Test #1: Alice 4
Test #2: Alice 4
Test #3: Alice 4
Test #4: Alice 5
Test #5: Alice 2
Test #6: Alice 2
Test #7: Bob
Test #8: Bob
Test #9: Alice 1
Test #10: Alice 3
C艹代码：
- #include <stdio.h>
- #include <math.h>
- #include <string.h>
- #define MIN 110000
- #define MAX 5000010
- int cnt,n,ans;
- int Count[MAX],arr[MIN];
- int pn,prime[MAX],Min_factor[MAX];
- void make_prime(){
- int i,j,x,pn = 0;
- for(i = 2; i < MAX; i++){
- if(!Min_factor[i]) prime[pn++] = i,Min_factor[i] = i;
- for(j = 0; j < pn && prime[j] * i < MAX; j++){
- x = prime[j] * i;
- Min_factor[x] = prime[j];
- if(i % prime[j] == 0) break; //确保不重复计算
- }
- }
- }
- int solve(int n){
- int ans = 0;
- while (n != 1){
- int t = 0;
- int k = Min_factor[n];
- while (n % k == 0)
- n /= k,t++;
- ans += t;
- }
- return ans;
- }
- int main()
- {
- int i,j,k,cas = 0;
- make_prime();
- while (scanf("%d",&n) != EOF) {
- ans = 0,Count[1] = 0;
- for (i = 1; i <= n; ++i) {
- scanf("%d",&arr[i]);
- arr[i] = solve(arr[i]);
- ans ^= arr[i];
- }
- printf("Test #%d: ",++cas);
- if (ans == 0) printf("Bob\n"); //P态
- else {
- for (i = 1; i <= n; ++i)
- if ((ans ^ arr[i]) < arr[i]) {//N态出现这状况必可以去掉一些而变为p态
- printf("Alice %d\n",i);
- break;
- }
- }
- }
- }