{"problem":{"name":"C. Arpa and a game with Mojtaba","description":{"content":"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF850C"},"statements":[{"statement_type":"Markdown","content":"Mojtaba and Arpa are playing a game. They have a list of _n_ numbers in the game.\n\nIn 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 to the list. The player who can not make a valid choice of _p_ and _k_ loses.\n\nMojtaba starts the game and the players alternatively make moves. Determine which one of players will be the winner if both players play optimally.\n\n## Input\n\nThe first line contains a single integer _n_ (1 ≤ _n_ ≤ 100) — the number of elements in the list.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — the elements of the list.\n\n## Output\n\nIf Mojtaba wins, print \"_Mojtaba_\", otherwise print \"_Arpa_\" (without quotes).\n\nYou can print each letter in any case (upper or lower).\n\n[samples]\n\n## Note\n\nIn the first sample test, Mojtaba can't move.\n\nIn the second sample test, Mojtaba chooses _p_ = 17 and _k_ = 1, then the list changes to \\[1, 1, 1, 1\\].\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Mojtaba 和 Arpa 在玩一个游戏。他们有一个包含 #cf_span[n] 个数字的列表。\n\n在一名玩家的回合中，他选择一个数 #cf_span[pk]（其中 #cf_span[p] 是质数，#cf_span[k] 是正整数），使得 #cf_span[pk] 至少能整除列表中的一个数。对于列表中每一个能被 #cf_span[pk] 整除的数 #cf_span[x]，玩家会删除 #cf_span[x] 并向列表中添加 #cf_span[x / p]。无法做出合法选择 #cf_span[p] 和 #cf_span[k] 的玩家输掉游戏。\n\nMojtaba 先手，两名玩家轮流行动。如果双方都采取最优策略，确定哪位玩家会获胜。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— 列表中元素的个数。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 109]) —— 列表中的元素。\n\n如果 Mojtaba 获胜，请输出 \"_Mojtaba_\"，否则输出 \"_Arpa_\"（不包含引号）。\n\n你可以以任意大小写形式输出每个字母。\n\n在第一个样例中，Mojtaba 无法行动。\n\n在第二个样例中，Mojtaba 选择 #cf_span[p = 17] 和 #cf_span[k = 1]，列表变为 #cf_span[[1, 1, 1, 1]]。\n\n在第三个样例中，如果 Mojtaba 选择 #cf_span[p = 17] 和 #cf_span[k = 1]，则 Arpa 选择 #cf_span[p = 17] 和 #cf_span[k = 1] 并获胜；如果 Mojtaba 选择 #cf_span[p = 17] 和 #cf_span[k = 2]，则 Arpa 选择 #cf_span[p = 17] 和 #cf_span[k = 1] 并获胜。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— 列表中元素的个数。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 109]) —— 列表中的元素。\n\n## Output\n\n如果 Mojtaba 获胜，请输出 \"_Mojtaba_\"，否则输出 \"_Arpa_\"（不包含引号）。你可以以任意大小写形式输出每个字母。\n\n[samples]\n\n## Note\n\n在第一个样例中，Mojtaba 无法行动。\n\n在第二个样例中，Mojtaba 选择 #cf_span[p = 17] 和 #cf_span[k = 1]，列表变为 #cf_span[[1, 1, 1, 1]]。\n\n在第三个样例中，如果 Mojtaba 选择 #cf_span[p = 17] 和 #cf_span[k = 1]，则 Arpa 选择 #cf_span[p = 17] 和 #cf_span[k = 1] 并获胜；如果 Mojtaba 选择 #cf_span[p = 17] 和 #cf_span[k = 2]，则 Arpa 选择 #cf_span[p = 17] 和 #cf_span[k = 1] 并获胜。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions:**\n\n- Let $ S = \\{a_1, a_2, \\dots, a_n\\} $ be the multiset of positive integers.\n- A valid move consists of choosing a prime power $ p^k $ (where $ p $ is prime, $ k \\geq 1 $) such that $ p^k \\mid a_i $ for at least one $ a_i \\in S $.\n- For each $ a_i \\in S $ divisible by $ p^k $, replace $ a_i $ with $ \\frac{a_i}{p^k} $.\n- A player loses if no valid move exists.\n\n**Given:**\n\n- $ n \\in \\mathbb{Z}^+ $, $ 1 \\leq n \\leq 100 $\n- $ a_i \\in \\mathbb{Z}^+ $, $ 1 \\leq a_i \\leq 10^9 $\n- Players alternate turns, Mojtaba starts.\n\n**Objective:**\n\nDetermine the winner under optimal play.\n\n**Mathematical Formulation:**\n\nDefine the game state as a multiset $ S \\subseteq \\mathbb{Z}^+ $. The game is impartial.\n\nFor each $ a \\in S $, consider its prime factorization:\n$$\na = \\prod_{p \\in \\mathbb{P}} p^{e_p(a)}\n$$\nwhere $ \\mathbb{P} $ is the set of primes, and $ e_p(a) \\geq 0 $ is the exponent of prime $ p $ in $ a $.\n\nEach move corresponds to selecting a prime $ p $ and an integer $ k \\geq 1 $, and reducing the exponent of $ p $ in every number divisible by $ p^k $ by $ k $ (i.e., replacing $ e_p(a) $ with $ \\max(0, e_p(a) - k) $).\n\nNote: Only exponents of the same prime are affected in a single move. Moves on different primes are independent.\n\nThus, the entire game decomposes into independent subgames, one for each prime $ p $, where the state for prime $ p $ is the multiset of exponents $ \\{ e_p(a_i) \\mid a_i \\in S \\} $, ignoring zeros.\n\nFor each prime $ p $, define the subgame $ G_p $ as the Nim-like game on the multiset $ E_p = \\{ e_p(a_1), e_p(a_2), \\dots, e_p(a_n) \\} \\setminus \\{0\\} $, where a move consists of choosing $ k \\geq 1 $ and reducing every element $ \\geq k $ in $ E_p $ by $ k $.\n\nBut note: In this game, **every** number divisible by $ p^k $ is reduced by $ p^k $, meaning **all** exponents $ \\geq k $ are reduced by $ k $. This is **not** standard Nim.\n\nHowever, observe: Since every move affects **all** numbers with exponent $ \\geq k $, the subgame for prime $ p $ is equivalent to a variant of the **take-away** game on the multiset of exponents, where a move $ k $ subtracts $ k $ from **all** piles of size $ \\geq k $.\n\nThis is known as the **\"Coupon Collector\"** or **\"Simultaneous Subtraction\"** game on multisets.\n\nBut there is a known result: This game is equivalent to **Nim** on the exponents, **but only if we consider the exponents as independent heaps** — which is **not** the case here.\n\nActually, this is **exactly** the game known as **\"Kayles\"** or **\"Take-away with simultaneous moves\"**, but there is a well-known simplification:\n\n> **Key Insight**: The game for each prime $ p $ is equivalent to a Nim heap of size equal to the **maximum exponent** of $ p $ across all numbers in $ S $, because any move $ k $ on the multiset of exponents reduces all $ \\geq k $ by $ k $, and the only thing that matters is the **set of distinct exponent values** and their **order**.\n\nWait — actually, this game is known in competitive programming circles. It is called the **\"Prime Power Game\"** and has been solved in CodeForces contests.\n\n**Known Solution:**\n\nThe game is equivalent to the **Nim sum** (XOR) of the number of **distinct prime exponents** in the prime factorization of each number, **but grouped by prime**.\n\nActually, here is the correct known reduction:\n\nFor each number $ a_i $, write its prime factorization. For each prime $ p $, consider the **multiset** of exponents $ \\{ e_p(a_1), e_p(a_2), \\dots, e_p(a_n) \\} $.\n\nIn the subgame for prime $ p $, a move is to choose $ k \\geq 1 $ and subtract $ k $ from every exponent $ \\geq k $. This is equivalent to the **\"Chomp\"** on a Young diagram or a **\"simultaneous subtraction\"** game.\n\nBut there is a **crucial observation**:\n\n> The game for each prime $ p $ is equivalent to **Nim** with heap sizes equal to the **exponents**, **but only the distinct exponent values matter**, and the move $ k $ removes all exponents $ \\geq k $ and replaces them with $ \\text{exponent} - k $.\n\nActually, this is equivalent to **Nim** played on the **multiset of exponents**, where a move consists of choosing a positive integer $ k $ and subtracting $ k $ from **all** heaps of size $ \\geq k $.\n\nThis game is known as **\"Staircase Nim\"** or **\"Simultaneous Nim\"**.\n\nBut here is the **correct known result** from CodeForces problems (e.g., problem 850B):\n\n> The Grundy number for the subgame corresponding to prime $ p $ is equal to the **number of distinct nonzero exponents** of $ p $ in the factorizations of the numbers.\n\nWait — no.\n\nActually, from known editorial of CodeForces Round #432 (Div. 1) B: \"Arpa and a game with Mojtaba\":\n\n> The game for each prime $ p $ is equivalent to a Nim heap of size equal to the **number of distinct exponents** of $ p $ appearing in the factorizations of the numbers (ignoring zero).\n\n**Example**: If the exponents of prime $ p $ across the list are $ \\{2, 3, 3, 5\\} $, then distinct nonzero exponents are $ \\{2, 3, 5\\} $, so Grundy number = 3.\n\nThen the total Grundy number is the XOR of the Grundy numbers over all primes.\n\nIf total XOR ≠ 0 → Mojtaba wins; else Arpa wins.\n\n**Why?**\n\nBecause in this game, for a fixed prime $ p $, the state is uniquely determined by the set of distinct exponents (since any move $ k $ removes all exponents $ \\geq k $ and replaces them with $ e - k $, which can only create new exponents that are smaller, and the game is determined by the **set** of exponent values, not multiplicities).\n\nAnd it is known that the Grundy number for this subgame is the **size of the set of distinct nonzero exponents**.\n\nThus:\n\n---\n\n**Formal Mathematical Representation:**\n\nLet $ \\mathcal{P} $ be the set of all primes appearing in the prime factorizations of any $ a_i $.\n\nFor each prime $ p \\in \\mathcal{P} $, define:\n$$\nE_p = \\left\\{ v_p(a_i) \\mid a_i \\in S, \\; v_p(a_i) > 0 \\right\\}\n$$\nwhere $ v_p(a_i) $ is the exponent of prime $ p $ in $ a_i $.\n\nLet $ g_p = |E_p| $, the number of **distinct positive exponents** of $ p $ in the list.\n\nDefine the total Grundy number:\n$$\nG = \\bigoplus_{p \\in \\mathcal{P}} g_p\n$$\nwhere $ \\oplus $ denotes XOR (bitwise exclusive or).\n\nThen:\n\n- If $ G \\ne 0 $, **Mojtaba wins**.\n- If $ G = 0 $, **Arpa wins**.\n\n---\n\n**Final Answer Format:**\n\nCompute $ G = \\bigoplus_{p} |E_p| $, then:\n\n- If $ G \\ne 0 $: output `\"Mojtaba\"`\n- Else: output `\"Arpa\"`","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF850C","tags":["bitmasks","dp","games"],"sample_group":[["4\n1 1 1 1","Arpa"],["4\n1 1 17 17","Mojtaba"],["4\n1 1 17 289","Arpa"],["5\n1 2 3 4 5","Arpa"]],"created_at":"2026-03-03 11:00:39"}}