ACdream 1112 Alice and Bob (sg函数的变形+素数筛)

题意:有N个数,Alice 和 Bob 轮流对这些数进行操作,若一个数 n=a*b且a>1,b>1,可以将该数变成 a 和 b 两个数;

或者可以减少为a或b,Alice先,问谁能赢

思路:首先单看对每个数进行除法的操作,我们可以知道其实是在除以每个数的素因子或素因子之间的积

比如 70=2*5*7 我们可以变成 10(2*5)或 14(2*7) 或 35(5*7)或 2 或 5 或 7 或 1 这七种状态

当我们把他们(2,5,7)当作3个石子也就是一堆时,然而实际上我们是将这堆石子进行nim游戏

我拿走一个石子 =》 10(2*5) 我拿走了石子7

14 (2*7) 我拿走了石子5

35 (5*7) 我拿走了石子2

我拿走两个石子 =》 2    我拿走了石子5 和 石子7

5    我拿走了石子2 和 石子7

7    我拿走了石子2 和 石子5

我拿走三个石子 =》 1     我拿走了石子2 和 石子5 和 石子7

接下来我们分析把一个数n=a*b变成 a 和 b ,其实这里上面的思想很像,把它当作石子的分堆

我可以分成             第一种 10(2*5) 和 7

第二种 14(2*7) 和 5

第三种 35(5*7) 和 2

综上所诉,根据正整数唯一分解定理,任何一个正整数x必然有x=(p1^r1)*(p2^r2)*......*(pn^rn)

定义sum=r1+r2+...+rn,这个sum的值就是这堆石子的总数,那么sg=sg[sum1]^sg[susm2]^....

问题又来了? 这个sum我们应该如何求呢?

我们可以通过素数筛得到每一个数的最小质因子,我们得到一个类似于递推的公式

一个正整数的质因子的个数=(这个正整数 / 这个数的最小质因子 所得数) 的质因子个数 + 1(也就是加上这是最小质因子的数量 1)

接下来代码实现就可以了

代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 5000000
using namespace std; int prime[maxn+],k=,samll[maxn],sum[maxn];
bool visit[maxn+];
int sg[]; void get_prime()
{
memset(visit,false,sizeof(visit));
memset(samll,,sizeof(samll));
memset(sum,,sizeof(sum));
for(int i=;i<=maxn;i++)
{
if(visit[i]==false)
{
prime[k++]=i;
for(int j=i+i;j<=maxn;j+=i)
{
visit[j]=true;
if(samll[j]==) samll[j]=i;
}
samll[i]=i;
}
}
for(int i=;i<=maxn;i++)
sum[i]=sum[i/samll[i]]+;
} int get(int n)
{
if(sg[n]!=-) return sg[n];
bool vis[];
memset(vis,false,sizeof(vis));
for(int i=;i<=n;i++)
vis[get(n-i)]=true;
for(int i=;i<=n/;i++)
vis[get(i)^get(n-i)]=true;
int k;
for(int i=;i<;i++)
{
if(vis[i]==false)
{
return sg[n]=i;
}
}
} int main()
{
get_prime();
memset(sg,-,sizeof(sg));
sg[]=;
sg[]=;
for(int i=;i<=;i++)
{
get(i);
}
int n;
while(cin>>n)
{
int ans=;
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
ans=ans^sg[sum[x]];
}
if(ans)
cout<<"Alice"<<endl;
else
cout<<"Bob"<<endl;
}
return ;
}
上一篇:Sublime Text 3 注册码 激活码 版本号 Build 3143


下一篇:[VS]VS2010如何使用Visual Studio Online在线服务管理团队资源(在线TFS)