题解：CF850C Arpa and a game with Mojtaba

maxiaomeng · 2025-12-05 16:41:03 · 题解

由于是博弈问题，考虑 SG 函数。

由于每个质因子独立，考虑对每个质因子求解 SG 函数，再异或起来。以下只对单个质因子考虑。

每次操作选择一个数 k，质因子个数大于等于 k 的数质因子个数减 k。

因为质因子个数相同的数操作后质因子个数也必然相同，只需用状压记录是否存在一个质因子个数为 i(i>0) 的数即可。

设状压状态为 S，则它可以转移到 (S\operatorname{rsh} k)\operatorname{or}\ (S\operatorname{and}\ (2^k-1)) \operatorname{and}\ (\operatorname{not}\ 1)。其中 \operatorname{rsh}、\operatorname{or} 和 \operatorname{and} 分别为按位右移、按位或和按位与。

记忆化搜索即可，虽然理论运行次数为指数级，但实际上跑得飞快。

:::info{code}

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=105;
int n,a[N],r;
map<int,int>mp,sg;
int dfs(int x){
    if(!x)return 0;
    if(sg.count(x))return sg[x];
    set<int>st;
    int z=63-__builtin_clzll(x);
    for(int i=1;i<=z;i++){
        int f=((x>>i)|(x&((1ll<<i)-1)))&~1;
        if(f<x)st.insert(dfs(f));
    }
    for(int i=0;i<=st.size();i++){
        if(!st.count(i))return sg[x]=i;
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        map<int,int>tmp;
        for(int j=2;j*j<=a[i];j++){
            if(a[i]%j==0){
                tmp[j]=0;
                while(a[i]%j==0)a[i]/=j,++tmp[j];
            }
        }
        if(a[i]!=1)tmp[a[i]]=1;
        for(auto j:tmp){
            if(!mp.count(j.first))mp[j.first]=(1ll<<j.second);
            else mp[j.first]|=(1ll<<j.second);
        }
    }
    for(auto i:mp)r^=dfs(i.second);
    cout<<"Arpa\0Mojtaba"+bool(r)*5<<'\n';
    return 0;
}

:::