题面:
题意:
给定一个长度为 n 的序列 a。
每次可以选择一个质数 p 和一个正整数 k,其中要保证 pk 要至少是当前序列 a 中某一个数的因子。然后把序列 a 中所有 pk 的倍数 ai 替换为 pkai。
两个人轮流操作,都采取最优的策略,谁不能进行操作就输了。
题解:
容易发现,对于序列 a 中的所有的数唯一分解之后出现的质数 p,不同的 p 相互独立。
则 anssg=sg(p1) xor sg(p2) xor....xor sg(pk)
我们只需要处理出对于每一个 pi 的 sg 函数然后异或起来即可。
求解 sg 函数时与具体的 pi 无关,只与每个数中所包含 pi的个数有关。
因为 ai≤1e9,唯一分解之后的某个数质因子的指数不会超过32,而且如果有两个数都含有 x 个质因子 p,那么与一个数含有 x 个质因子 p 另一个数不含有质因子 p 是一致的。所以我们可以状压记录当前状态。
代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
//#define max(x,y) ((x)>(y)?(x):(y))
//#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxm=100100;
const int maxp=100100;
const int up=100100;
int prime[maxn],cnt=0;
bool ha[maxn];
void Prime(void)
{
ha[1]=true;
for(int i=2;i<maxn;i++)
{
if(!ha[i])
prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<maxn;j++)
{
ha[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
}
int a[200];
int n;
map<int,int>mp;
void only(int x)
{
for(int i=1;i<=cnt&&prime[i]*prime[i]<=x;i++)
{
if(x%prime[i]) continue;
int pm=0;
while(x%prime[i]==0)
{
pm++;
x/=prime[i];
}
mp[prime[i]]|=(1<<pm);
}
if(x>1) mp[x]|=(1<<1);
}
map<int,int>mmp;
int get_sg(int x)
{
if(x==0||x==1) return 0;//x==1-->p^0
if(mmp.count(x)) return mmp[x];
bool ha[55];
memset(ha,0,sizeof(ha));
for(int i=1;i<=32;i++)
{
if((x>>i)==0) break;
ha[get_sg((x>>i)|(x&((1<<i)-1)))]=true;
}
for(int i=0;;i++)
{
if(!ha[i])
return mmp[x]=i;
}
}
int main(void)
{
Prime();
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
only(a[i]);
}
int ans=0;
for(auto it=mp.begin();it!=mp.end();it++)
ans^=get_sg(it->second);
if(ans) printf("Mojtaba\n");
else printf("Arpa\n");
return 0;
}