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 ;

}

巴特西

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

最新文章

热门文章