ACdream 1112 Alice and Bob (博弈&&素数筛选优化)

题目链接：传送门

游戏规则：

没次可以将一堆分成两堆 x = a*b （a!=1&&b!=1）x为原来堆的个数,a,b为新堆的个数。

也可以将原来的堆的个数变成原来堆的约数y，y!=x。进行最后一次操作的人获胜。

分析：

也是一个去石头的游戏，因此我们只需要将所有情况的sg值异或起来就好了。

我们首先来考虑一堆。设这一堆的个数为x；

那么所有的情况就是

（a1,x/a1）, (a2,x/a2),...,(an,x/an);或者（a1),(a2),..,(an)。

由于数据量比较大，我们朴素的找约数肯定会超时。然后仔细分析一下这个问题。因为我

们都是围绕着约数来进行操作，那么也就相当于在对他的素因子的个数进行操作。

x=a1^r1*a2^r2*...*an^rn;设sum = r1+r2+...+rn.

然后所有的情况就可以表示为：

（1，sum-1）,(2,sum-2),...(sum/2,sum-sum/2)或者(1),(2),...(n-1)

这样就大大减小了数据的范围。然后在计算sum的时候我们可以这样计算。

设一个数为x，他的最小的素因子为y.则sum[x] = sum[x/y] + 1;

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int maxn = 5000010; int prime[maxn],cnt; bool isprime[maxn]; int fac_num[maxn]; int min_fac[maxn]; int sg[100]; void GetPirme(){ cnt=0; memset(isprime,0,sizeof(isprime)); memset(fac_num,-1,sizeof(fac_num)); memset(min_fac,-1,sizeof(min_fac)); for(int i=2;i
      
       
?