# Arpa and a Game with Mojtaba

## 题目描述

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 ${x \over p^k}$ 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.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

namespace std {
template <typename T>
void maxify(T &a, T b) { b > a && (a = b); }
template <typename T>
void minify(T &a, T b) { b < a && (a = b); }
}

struct IOManager {
template <typename T>
char c; bool flag = false; x = 0;
while (~ c && ! isdigit(c = getchar()) && c != '-') ;
c == '-' && (flag = true, c = getchar());
if (! ~ c) return false;
while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
return (flag && (x = -x), true);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
char c; int len = 0;
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
if (! ~ c) return 0;
while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
return (s[len] = '\0', len);
}
template <typename T>
inline IOManager operator > (T &x) {
}
template <typename T>
inline void write(T x) {
x < 0 && (putchar('-'), x = -x);
x > 9 && (write(x / 10), true);
putchar(x % 10 + '0');
}
inline void write(char c) {
putchar(c);
}
inline void write(char s[]) {
int pos = 0;
while (s[pos] != '\0') putchar(s[pos ++]);
}
template <typename T>
inline IOManager operator < (T x) {
write(x); return *this;
}
} io;

struct Solver {
private:
static const int N = 100;
int n, a[N + 1];
map <int, int> sg, num;
void input() {
io > n;
for (int i = 1; i <= n; ++ i) io > a[i];
}
void init() {
for (int i = 1; i <= n; ++ i)
if (a[i] > 1) {
int q = sqrt(a[i]);
for (int j = 2; j <= q; ++ j) {
if (a[i] == 1) break;
if (! (a[i] % j)) {
int cnt = 0;
while (! (a[i] % j)) a[i] /= j, ++ cnt;
num[j] |= 1 << cnt - 1;
}
}
if (a[i] > 1) num[a[i]] |= 1;
}
}
int get_sg(int t) {
if (! t) return 0;
if (sg.count(t)) return sg[t];
map <int, bool> vis;
int p = t, cnt = 0;
while (p) p >>= 1, ++ cnt;
for (int i = 1; i <= cnt; ++ i)
vis[get_sg((t >> i) | (t & (1 << i - 1) - 1))] = true;
cnt = 0;
while (vis[cnt]) ++ cnt;
return sg[t] = cnt;
}
void process() {
int ans = 0;
for (map <int, int> :: iterator it = num.begin(); it != num.end(); ++ it) ans ^= get_sg(it->second);
if (! ans) io < (char *) "Arpa\n";
else io < (char *) "Mojtaba\n";
}

public:
void solve() {
input(), init(), process();
}
} solver;

int main() {
solver.solve();
return 0;
}


418 I'm a teapot