#P9245. 最大公约数游戏

    ID: 5365 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高+/省选-奇偶性分析必胜/必败状态递推欧几里得算法

最大公约数游戏

题面翻译

题目描述

黑板上写着 N N 个整数。第 i i 个整数是 Ai A_i ,它们的最大公约数为 1 1 。

高桥君和青木君将使用这些数来玩一个游戏。高桥君在这个游戏中是先手,他们将轮流进行以下操作(以下两步相当于一次操作):

  • 选择黑板中大于 1 1 的一个数,将其减 1 1 。
  • 此后,将黑板上所有数全部除以所有数的最大公约数。

当黑板上的数全部为 1 1 时,不能再进行操作的人就失败了。两人都选择最好的方式行动,请求出哪边会最终胜利。

数据范围

  • 1≤N≤105 1 \leq N \leq 10^5
  • 1≤Ai≤109 1 \leq A_i \leq 10^9
  • 从 A1 A_1 到 AN A_N 的所有数的最大公约数为 1 1 。

输入

第一行给出N

第二行给出N个数字

输出

如果先手的高桥君获胜了,则输出First。如果后手的青木君获胜了,则输出Second。

样例 #1

样例输入 #1

3
3 6 7

样例输出 #1

First

样例 #2

样例输入 #2

4
1 2 4 8

样例输出 #2

First

样例 #3

样例输入 #3

5
7 8 8 8 8

样例输出 #3

Second

样例1解释

按以下情况高桥君将胜利:

  • 高桥君将 7 7 减去 1 1 。操作后黑板上的数为 (1,2,2) (1,2,2) 。
  • 青木君将 2 2 减去 1 1 。操作后黑板上的数为 (1,1,2) (1,1,2) 。
  • 高桥君将 2 2 减去 1 1 。操作后黑板上的数为 (1,1,1) (1,1,1) 。