만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

최대공약수 게임

시간 제한3초메모리 제한1024 MB

요약
두 사람이 번갈아 카드를 골라 칠판 수와의 최대공약수가 1이 되지 않게 할 때, 누가 이기는지 구합니다.
난이도

보통10점 중 7점

유형
게임 이론, 정수론, 동적 계획법
정답자
아직 제출이 없습니다

문제

철수와 영희는 NN개의 카드로 구성된 카드 뭉치와 칠판을 가지고 최대공약수 카드 게임을 한다.

각 카드에는 11번부터 NN번까지 번호가 매겨져 있고, ii번 카드에는 양의 정수 AiA_i가 적혀 있다. 칠판에는 22 이상의 정수 XX가 적혀 있다. 게임은 철수부터 시작하며, 각 차례마다 플레이어는 아래 과정을 수행한다.

  1. 카드 뭉치에서 카드를 하나 고른다. 이때 칠판에 적힌 수와 고른 카드에 적힌 수의 최대공약수가 11이면 안 된다.
  2. 칠판에 적힌 수와 카드에 적힌 수의 최대공약수를 칠판에 새로 적고, 원래 칠판의 수는 지운다.
  3. 고른 카드는 카드 뭉치에서 뺀다.

자신의 차례에 고를 수 있는 카드가 없으면 패배한다. 카드 뭉치가 비었거나, 어떤 카드를 고르더라도 칠판의 수가 11이 되는 경우가 여기에 해당한다. 철수와 영희는 최선의 전략을 알고 있으며 이를 따라 게임에 참여한다. 칠판의 수와 카드 조합이 주어졌을 때 승자를 가려라.

입력

첫 번째 줄에 카드의 수 NN과 칠판에 적힌 양의 정수 XX가 공백으로 구분되어 주어진다. (1≤N≤3001 \leq N \leq 300; 2≤X≤1092 \leq X \leq 10^9)

두 번째 줄에 카드에 적힌 양의 정수 A1,A2,…,ANA_1, A_2, \dots, A_N가 공백으로 구분되어 주어진다. (1≤Ai≤1091 \leq A_i \leq 10^9)

출력

철수가 이긴다면 First, 영희가 이긴다면 Second를 출력한다.

예제3

  1. 예제 1

    입력
    5 10
    2 5 15 25 35
    
    예상 출력
    First
    
  2. 예제 2

    입력
    4 6
    2 2 3 3
    
    예상 출력
    Second
    
  3. 예제 3

    입력
    5 3
    3 3 3 3 3
    
    예상 출력
    First