Arpa and a game with Mojtaba
题意翻译
Mojtaba和Arpa在玩一个游戏。
游戏中有一个n个数的数列,在一个回合中,他可以选取一个形如$p^k$的数,其中$p$是个质数,而$k$是一个正整数,并且满足这个数列中至少有一个数能被它整除。每一个回合结束时将整个数列中所有的能被这个数整除的数都将除以这个数。
(例如数列{$1$,$1$,$17$,$289$}.如果选取了$17$,经过一个回合之后数列将变成{$1$,$1$,$1$,$17$})
而游戏胜负的条件是有一个人如果无法选出这样一个数就输了。
游戏中Mojtaba先手,游戏双方都将用最优策略,输出胜利者的名字
输入格式:
第一行n,表示这个数列的长度
第二行n个数,表示这个数列
输出格式:
一个名字,无论大小写(即答案如果是Arpa,arpa,ARPA,aRpA都可)
说明:
第一个样例中Mojtaba无法选取任何数字,Arpa胜;
第二个样例中Mojtaba选取$17$($17^1$),数列变为{$1$,$1$,$1$,$1$},Arpa无法选取,Mojtaba胜;
第三个样例中Mojtaba选取$17$($17^1$),Arpa选取$17$($17^1$),胜。或者Mojtaba选取$289$($17^2$),Arpa选取$17$($17^1$)胜。
题目描述
Mojtaba and Arpa are playing a game. They have a list of $ n $ numbers in the game.
In a player's turn, he chooses a number $ p^{k} $ (where $ p $ is a prime number and $ k $ is a positive integer) such that $ p^{k} $ divides at least one number in the list. For each number in the list divisible by $ p^{k} $ , call it $ x $ , the player will delete $ x $ and add ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF850C/850f475308e1a5d29f90bf50cce5258d86ba6e49.png) to the list. The player who can not make a valid choice of $ p $ and $ k $ loses.
Mojtaba starts the game and the players alternatively make moves. Determine which one of players will be the winner if both players play optimally.
输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 1<=n<=100 $ ) — the number of elements in the list.
The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ) — the elements of the list.
输出格式
If Mojtaba wins, print "Mojtaba", otherwise print "Arpa" (without quotes).
You can print each letter in any case (upper or lower).
输入输出样例
输入样例 #1
4
1 1 1 1
输出样例 #1
Arpa
输入样例 #2
4
1 1 17 17
输出样例 #2
Mojtaba
输入样例 #3
4
1 1 17 289
输出样例 #3
Arpa
输入样例 #4
5
1 2 3 4 5
输出样例 #4
Arpa
说明
In the first sample test, Mojtaba can't move.
In the second sample test, Mojtaba chooses $ p=17 $ and $ k=1 $ , then the list changes to $ [1,1,1,1] $ .
In the third sample test, if Mojtaba chooses $ p=17 $ and $ k=1 $ , then Arpa chooses $ p=17 $ and $ k=1 $ and wins, if Mojtaba chooses $ p=17 $ and $ k=2 $ , then Arpa chooses $ p=17 $ and $ k=1 $ and wins.