Description
两个人Van♂游戏。给出$n$个正整数$ai$两人轮流操作，每次选出一个素数$p$和一个幂数$k$，选择的前提为该$n$个数中有$p^{k}$的倍数。接着将所有的$p^{k}$的倍数除以$p^{k}$。变成新的序列，继续操作。不能操作者为败，问先手是否必胜。
1≤100≤n,1≤ai≤109
Examples
Input
4
1 1 1 1
Output
Arpa
Input
4
1 1 17 17
Output
Mojtaba
Input
4
1 1 17 289
Output
Arpa
Input
5
1 2 3 4 5
Output
Arpa
不同质因数不互相影响
于是分开讨论每个质因数的SG值
压缩状态，如果一个数含有k个p
即$a[i]%p^{k}==0$
那么状态中第k-1位为1
那么枚举每一次的k，求出SG值
最后将每个质因数的答案取Nim和
不过状态可能会很大，用map
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
map<int,int>sg;
int n,a[],pri[],Max[],cnt,ans;
map<int,int>vis;
int qpow(int x,int y)
{
int res=;
while (y)
{
if (y&) res=res*x;
x=x*x;
y>>=;
}
return res;
}
int get_SG(int S)
{int i,p,SS,t;
if (sg.count(S)) return sg[S];
if (S==) return ;
map<int,int>v;
t=;SS=S;
while (SS)
{
SS>>=;
t++;
}
for (i=;i<t;i++)
{
p=i+,SS=S;
v[get_SG((SS>>p)|(((<<p-)-)&S))]=;
}
for (p=;;p++)
if (v.count(p)==) break;
return sg[S]=p;
}
int main()
{int i,j,tot,k;
cin>>n;
for (i=;i<=n;i++)
{
scanf("%d",&a[i]);
int x=a[i],k=sqrt(x);
for (j=;j<=k;j++)
{tot=;
while (x%j==)
{
tot++;
if (vis[j]==) pri[++cnt]=j,vis[j]=cnt;
x/=j;
}
Max[vis[j]]=max(tot,Max[vis[j]]);
}
if (x!=)
{
if (vis[x]==) pri[++cnt]=x,vis[x]=cnt;
Max[vis[x]]=max(Max[vis[x]],);
}
}
ans=;
for (i=;i<=cnt;i++)
{
sg.clear();
int S=;
for (j=;j<=n;j++)
{
for (k=Max[i];k>=;k--)
{
if (a[j]%qpow(pri[i],k)==)
{
S|=(<<k-);
break;
}
}
}
ans^=get_SG(S);
}
if (ans==) printf("Arpa\n");
else printf("Mojtaba\n");
}