codeforces 850C Arpa and a game with Mojtaba(博弈，bitmask)

╰半橙微兮° 2022-06-09 13:06 156阅读 0赞

![这里写图片描述][SouthEast]  
![这里写图片描述][SouthEast 1]

**题意**：给你n个数，a1，a2，……，an，两人轮流从中改数，每次选一个素数p和一个正整数k，将a1到an中所有可以被p^k整除的数除p^k。当玩家在他的回合把所有数都变成1后，该玩家就赢了。

**思路**：因为p只能是素数，所以我们可以把a1到an全部分解成素因数，不同的素数之间互相不影响，比如说2，3，4，6，我如果p选2，k选1，就变成了1，3，2，3。对p为3的时候是没有任何影响的。所以说我们只要把每一个素数的SG值算出来然后异或就是答案了。  
接下来就要解决如何对单个素数求SG值。首先我们要把a1到an的数组处理成因子只有当前的这个素数的数组。比如2，3，4，6，当p=2的时候，我们就把它处理成2^1，2^0，2^2，2^1，也就是1，0，2，1，因为a1到an中所有可以被p^k整除的数都要除p^k，所以对于因子p的个数相同的数我们是可以视为一个数的。所以当我选2^1的时候，1，0，2，1就变成了0，0，1，0。这两个1的变化在任何时候都是一样的，所以说这两个1可以看作一个1。那么我们可以根据这一点来定义一个state：**state的第i位为真，当且仅当当前状态下存在一个数等于p^i。**比如：1，0，2，1的state值就等于1+2=3。1，2，2，3，3，5的state值就等于1+2+4+16=23。  
而对于每一个state，要从1到它的最大位数枚举k，对于每一个k，大于等于k的位数，都要减k（将a1到an中所有可以被p^k整除的数除p^k），比如1，2，2，3，3，5当k为3的时候后续状态就是1，2，2，0，0，2。  
**所以(state >> k) | (state&((1 << k-1) - 1))是state的后续状态。**  
然后这题就可以解出来了，需要注意的是要用map来存SG函数的值。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100007;
    const int MOD = 30021;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    map<int, int> SG,num;
    
    int getSG(int x)
    {
        if (x == 0)
            return 0;
        if (SG.count(x))
            return SG[x];
        map<int, int> vis;
        int p = x;
        int t=0;
        while (p)//计算最大位数
            p /= 2,t++;
        for (int k = 1; k <= t; k++)
            vis[getSG((x >> k) | (x&((1 << k-1) - 1)))] = 1;//后续状态
        for (int i = 0;; i++)
            if (!vis[i])
                return SG[x]=i;
    }
    
    int prime[MAXN], primesize;
    bool isprime[MAXN];
    void getlist(int listsize)//素数打表
    {
        memset(isprime, 1, sizeof(isprime));
        isprime[1] = false;
        for (int i = 2; i <= listsize; i++)
        {
            if (isprime[i])prime[++primesize] = i;
            for (int j = 1; j <= primesize&&i*prime[j] <= listsize; j++)
            {
                isprime[i*prime[j]] = false;
                if (i%prime[j] == 0)break;
            }
        }
    }
    
    void solve()//将读入的x分解素因数
    {
        int t,x;
        scanf("%d", &x);
        for (int i = 1; prime[i]*prime[i] <= x; i++)
        {
            t = 0;
            while (x%prime[i] == 0)
                x /= prime[i], t++;//计算x是p的几次方
            if(t!=0)
                num[prime[i]] = num[prime[i]] | 1 << (t - 1);//该数等于p^t，所以第t位为真
        }
        if (x != 1)
            num[x] = num[x] | 1;
    }
    
    int main()
    {
        getlist(100005);
        int n;
        int x;
        int ans = 0;
        scanf("%d", &n);
        while (n--)
            solve();
        map<int, int>::iterator it;
        for (it = num.begin(); it != num.end(); it++)
            ans ^= getSG(it->second);
        if (ans == 0)
            printf("Arpa\n");
        else
            printf("Mojtaba\n");
    }

[SouthEast]: /images/20220609/36c3c84cab934e8ea9b2063aef09d156.png
[SouthEast 1]: /images/20220609/5e6d848c9a5d4a15a694629363b4bcb6.png