本题涉及博弈论中的Nim游戏博弈。
Nim游戏博弈详解链接：
http://www.cnblogs.com/exponent/articles/2141477.html
本题解题报告详解链接：
http://blog.csdn.net/woshi250hua/article/details/7824609
我的代码，写的较挫，4000多ms，压着时间过，时间限制是5s.我预处理了所有1-5*10^6的数的素因子个数，用的是dp
的思想，先预处理1-5*10^6的数的最小素因子，存在a数组中，然后dp[i] = dp[i/a[i] ]+1;
我觉得我代码最挫的地方是在求最小素因子时费时太多。。。。
#include <cstdio>
#define N 5000005
#define INF 0x7fffffff
int p[N];//每个数有多少个素数因子
int a[N];//每个数最小的素数因子
int prime[];//存素数表
void init()
{
//打素数表，求出1-5005以内的素数和每个数的最小质因子
for(int i=; i<; ++i)
prime[i] = INF;
prime[] = ;
int num = ;
for(int i=; i<; ++i)
{
int x = ;
while(i%prime[x] && prime[x] <= i) ++x;
if( !(i%prime[x]) )
a[i] = prime[x];
else
{
prime[++num] = i;
a[i] = i;
}
}
a[] =;
for(int i=; i< N; ++i)
{
int x = ;
while(i%prime[x] && prime[x] <= i) ++x;
if( !(i%prime[x]) )
a[i] = prime[x];
else
a[i] = i;
}
p[] = ;
for(int i=; i <N; ++i)
p[i] = p[i/a[i]] + ;
}
int main()
{
// freopen("in.cpp","r",stdin);
init();
int n;
int b[];
int t=;
while(scanf("%d",&n) != EOF)
{
int ans ;
for(int i=; i<n; ++i)
{
scanf("%d",&b[i]);
if(i)
ans ^= p[b[i]];
else
ans = p[b[i]];
}
printf("Test #%d: ",++t);
if(ans)
{
int index;
for(int i=; i<n; ++i)
if( (p[b[i]]^ans) < p[b[i]] )
{
index = i+;
break;
}
printf("Alice %d\n",index);
}
else printf("Bob\n");
}
return ;
}
这是改进后的代码，用线性筛法在打素数表的同时求出最小素因子····
初始化时每个数的最小素因子就是本身。
#include <cstdio>
#define N 5000005
#define INF 0x7fffffff
int p[N];//每个数有多少个素数因子
bool v[N]; //是否为素数
int a[N];//每个数最小的素数因子
int prime[N/];//素数表
//用打素数表的筛法求每个数的最小质因子
void init()
{
for(int i=; i<N; ++i)
a[i] = i;
int num=-;
for(int i=; i<N; ++i)
{
if(!v[i]) prime[++num] = i;
for(int j=; j<=num && i*prime[j] < N; ++j)
{
int t = i*prime[j];
v[t] =;
if(a[t] > prime[j]) a[t] = prime[j];
if(i%prime[j] == ) break;
}
}
p[] = ;
for(int i=; i <N; ++i)
p[i] = p[i/a[i]] + ;
} int main()
{
// freopen("in.cpp","r",stdin);
init();
int n;
int b[];
int t=;
while(scanf("%d",&n) != EOF)
{
int ans ;
for(int i=; i<n; ++i)
{
scanf("%d",&b[i]);
if(i)
ans ^= p[b[i]];
else
ans = p[b[i]];
}
printf("Test #%d: ",++t);
if(ans)
{
int index;
for(int i=; i<n; ++i)
if( (p[b[i]]^ans) < p[b[i]] )
{
index = i+;
break;
}
printf("Alice %d\n",index);
}
else printf("Bob\n");
}
return ;
}