#arc155d. [arc155_d]Avoid Coprime Game
[arc155_d]Avoid Coprime Game
题目描述
对于两个非负整数和, 表示和的最大公约数(当时,)。
黑板上有 个整数,第 个整数为 。这 个整数的最大公约数是 。
高桥和青木将互相进行游戏。在将一个整数 初始化为 后,他们轮流执行以下操作,高桥先开始。
- 选择黑板上的一个数 ,使得 ,擦除它,并用 替换 。
首先无法进行操作的一方输掉游戏。
对于每个 ,确定高桥在他的第一回合中选择黑板上的第 个整数后,双方都采取最优策略时的获胜者。
约束条件
- 这 个整数 的最大公约数是 。
- 输入中的所有值都是整数。
输入
输入以以下格式从标准输入给出:
输出
打印 行。第 行应包含获胜者的名字,Takahashi
或 Aoki
,表示高桥在他的第一个回合中选择黑板上的第 个整数后,双方都采取最优策略时的结果。
示例输入1
示例输出1
例如,当高桥在他的第一个回合中选择第四个整数 时,青木可以选择第二个整数 ,使得 。现在,高桥无法再进行选择,所以青木获胜。因此,第四行应包含 Aoki
。
示例输入2
示例输出2
黑板上可能会有相同的整数多次出现。