#P13653. [ARC155D] Avoid Coprime Game

    ID: 12855 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-必胜/必败状态递推状态维度消除奇偶性分析倍数枚举莫比乌斯反演

[ARC155D] Avoid Coprime Game

题目描述

对于两个非负整数 x,yx, y,gcd⁡(x,y)\gcd(x, y) 表示 xx 和 yy 的最大公约数(其中,当 x=0x=0 时,gcd⁡(x,y)=gcd⁡(y,x)=y\gcd(x, y)=\gcd(y, x)=y)。

黑板上写有 NN 个整数,第 ii 个整数为 AiA_i。这 NN 个整数的最大公约数为 11。

高桥君和青木君进行一场对战游戏。初始时整数 G=0G=0,两人轮流操作,高桥君先手。每次操作如下:

  • 从黑板上选择一个满足 gcd⁡(G,a)≠1\gcd(G, a) \neq 1 的数 aa,将其擦去,并用 gcd⁡(G,a)\gcd(G, a) 替换 GG。

无法进行操作的一方判负。

对于每个 i (1≤i≤N)i\ (1\leq i \leq N),请判断如果高桥君在第一回合选择第 ii 个整数,之后双方都采取最优策略,最终谁会获胜。

输入格式

输入通过标准输入给出,格式如下:

NN A1A_1 A2A_2 …\dots ANA_N

输出格式

输出 NN 行。第 ii 行输出高桥君在第一回合选择第 ii 个整数后,双方都采取最优策略时的胜者。如果高桥君获胜,输出 Takahashi;如果青木君获胜,输出 Aoki。

输入输出样例 #1

输入 #1

4
2 3 4 6

输出 #1

Takahashi
Aoki
Takahashi
Aoki

输入输出样例 #2

输入 #2

4
2 155 155 155

输出 #2

Takahashi
Takahashi
Takahashi
Takahashi

输入输出样例 #3

输入 #3

20
2579 25823 32197 55685 73127 73393 74033 95252 104289 114619 139903 144912 147663 149390 155806 169494 175264 181477 189686 196663

输出 #3

Takahashi
Aoki
Takahashi
Aoki
Takahashi
Takahashi
Takahashi
Takahashi
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Aoki
Takahashi
Takahashi
Aoki
Takahashi

说明/提示

限制条件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 2≤Ai≤2×1052 \leq A_i \leq 2 \times 10^5
  • NN 个整数 Ai (1≤i≤N)A_i\ (1\leq i \leq N) 的最大公约数为 11
  • 输入均为整数

样例解释 1

例如,如果高桥君在第一回合选择第 44 个整数 A4=6A_4=6,青木君可以选择第 22 个整数 A2=3A_2=3,此时 G=3G=3。之后高桥君无法再选择任何整数,因此青木君获胜。所以第 44 行应输出 Aoki。

样例解释 2

黑板上可能会有多个相同的整数。