題目大意：給定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艹代碼：
[cpp]
#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); www.2cto.com
break;
}
}
}
}
作者：woshi250hua
