ACdream 1112 Alice and Bob （SG函数）

淩亂°似流年 2022-06-11 00:40 142阅读 0赞

题目链接：  
[ACdream 1112][]

题意：  
给你n 堆石子，每次要按照规则将该堆石子的个数分为两堆或者将该堆石子的个数减少，谁不能继续操作了谁就输。  
规则如下：  
若n=a∗b  且a>1，b>1 ，可以将石子分为 a，b  两堆；或者可以减少为 a  或 b  。比如n=6 ，可以分为(2,3)，2,3 这三种情况，但是不能分为(1,6),1,6 这三种情况。

题解：  
对于n 个数，相当于n 个局面，只要将n 个局面异或起来就好了，所以我们就考虑一个数的时候的情况。  
对每个数的素因子个数进行操作，即素数可以看做是一个1。  
如果我们把x 写成质数的幂相乘的形式就是p a 1  1 ∗p a 2  2 ∗p a 3  3 …∗p a m  m    
sum=a 1 \+a 2 \+a 3 \+….a m ;   
然后所有的情况就可以表示为：  
（1，sum−1）,(2,sum−2),...(sum/2,sum−sum/2) 或者(1),(2),...(n−1)   
然后在计算sum 的时候我们可以这样计算。  
设一个数为x ，他的最小的素因子为 y . 则sum\[x\]=sum\[x/y\]\+1   
操作的本质其实就是给一些指数降幂，也就是可以把sum 变成(0–>sum−1) 中的任何一个数，或者变成h 1 ,h 2  的形式，h 1 \+h 2 =sum   
h 1 ,h 2  分别是两个因子对应的sum ，相当于sum 这个局面可以变成若干的子局面。用SG搞搞就可以了。  
SG 其实就是在子局面中找一个最小的未被访问过的数当做当前局面的值，如果你只想套结论的话这样就够用了。

AC代码：

/*
    * this code is made by LzyRapx
    * Problem: 1112
    * Verdict: Accepted
    * Submission Date: 2017-07-24 17:34:31
    * Time: 1368MS
    * Memory: 21196KB
    */
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 5000005;
    int flag[N];
    int sg[100], n;
    bool vis[100];
    
    void make_prime()
    {
        for(int i = 2; i < N; i++)
        {
            if(!flag[i])
            {
                for(int j = i + i; j < N; j += i) flag[j] = i;
            }
        }
    
    }
    void SG()
    {
        sg[0] = 0;
        for(int i = 1; i < 100; i++)
        {
            memset(vis, false, sizeof(vis));
            for(int j = 0; j < i; j++)
            {
                vis[sg[j]] = true;
            }
            for(int j = 1; j < i; j++){
                vis[sg[j] ^ sg[i - j]] = true;
            }
            for(int j = 0;;j++)
            {
                if(!vis[j])
                {
                    sg[i] = j;
                    break;
                }
            }
        }
    }
    int solve(int x)
    {
        int ret = 0;
        while(flag[x]){
            ret ++;
            x /= flag[x];
        }
        return ret + 1;
    }
    int main()
    {
        SG();
        make_prime();
        while(~scanf("%d", &n))
        {
            int ans = 0;
            for(int i = 0, x; i < n; i++)
            { 
                scanf("%d", &x);
                int cnt = solve(x);
                ans ^= sg[cnt];
            }
            puts(ans ? "Alice" : "Bob");
        }
        return 0;
    }

[ACdream 1112]: http://acdream.info/problem?pid=1112