← 返回题目列表

AtCoder · ttpc2019_d

D. 素数游戏

中文机器翻译题面 查看原题

配点: 100点

問題文

东京工业大学的学生小安正在和小爱玩一种名为“拿石头”游戏的两人游戏,但她对此感到厌倦,因为她知道获胜公式。

因此,安妮想出了一个专注于素数的游戏,并将其命名为“素数游戏”。

素数游戏规则如下。

  • 在开始时 有 N 山,i 第二座山是 X_i 個(X_i 是质数)
  • 两名玩家轮流选择其中一堆装有石子的石子,并从中取出一些石子。
  • 一次可以取的石子数是质数,堆中剩余的石子数也是 必须是 0 或素数
  • 第一个无法拿走任何石子的玩家失败。

这是一条新规则,但小安和小爱似乎立刻就想出了获胜的方法。

所以小安是第一推动者,小爱是第二推动者。 由 X_1 個, X_2 個, \ldots , X_N 石头组成 N 当玩素数游戏时,有一堆

制約

  • 所有输入均为整数
  • 1 \le N \le 2 \times 10^5
  • 2 \le X_i \le 10^6
  • X_i 是质数 答案可以由

入力

输入是按以下格式从标准输入给出的。

N
X_1 X_2 \ldots X_N

出力

如果先走的安酱获胜 An如果抽奖的小爱获胜 Ai 。


入力例 1

1
13

出力例 1

An
  • Ann-chan,第一个玩家,首先从山上开始。 只需拿走所有 13 碎片即可。

入力例 2

2
17 13

出力例 2

An
  • 第一位玩家小安从第二座山开始。 如果你拿走 2 棋子,抽签的爱酱只能拿走第一堆或第二堆中的所有东西,所以安酱获胜。

入力例 3

6
49529 868033 52361 519803 19289 386501

出力例 3

Ai