Problem:
 Score : 1000 points    Problem Statement There are N integers written on a blackboard. The i -th integer is A_i , and the greatest common divisor of these integers is 1 .  Takahashi and Aoki will play a game using these integers. In this game, starting from Takahashi the two player alternately perform the following operation:   Select one integer on the blackboard that is not less than 2 , and subtract 1 from the integer.  Then, divide all the integers on the black board by g , where g is the greatest common divisor of the integers written on the blackboard.   The player who is left with only 1 s on the blackboard and thus cannot perform the operation, loses the game.
Assuming that both players play optimally, determine the winner of the game.      Constraints  1 ≦ N ≦ 10^5  1 ≦ A_i ≦ 10^9  The greatest common divisor of the integers from A_1 through A_N is 1 .         Input The input is given from Standard Input in the following format:  N  A_1  A_2 … A_N       Output If Takahashi will win, print First . If Aoki will win, print Second .        Sample Input 1 3
3 6 7      Sample Output 1 First  Takahashi, the first player, can win as follows:   Takahashi subtracts 1 from 7 . Then, the integers become: (1,2,2) .  Aoki subtracts 1 from 2 . Then, the integers become: (1,1,2) .  Takahashi subtracts 1 from 2 . Then, the integers become: (1,1,1) .        Sample Input 2 4
1 2 4 8      Sample Output 2 First       Sample Input 3 5
7 8 8 8 8      Sample Output 3 Second

Solution (Python):
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  

N = I()
A = LI()

if N == 1:
    print('Second')
    exit()

if N == 2:
    print('First')
    exit()

from math import gcd

r = 0  
while True:
    if (sum(A)-N) % 2 == 1:
        if r == 0:
            print('First')
        else:
            print('Second')
        break
    else:
        a = 0  
        b = 0  
        for i in range(N):
            if A[i] % 2 == 1:
                a += 1
            if A[i] == 1:
                b += 1
        if a != 1 or b > 0:
            if r == 0:
                print('Second')
            else:
                print('First')
            break
        else:
            g = 0
            for i in range(N):
                if A[i] % 2 == 1:
                    g = gcd(g,A[i]-1)
                else:
                    g = gcd(g,A[i])
            for i in range(N):
                A[i] = A[i]//g
            r = 1-r

Solution (Python):
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
def gcds(ls):
  ret = 0
  for i in ls:
    ret = gcd(ret,i)
  return ret
def flg(ls):
  if (sum(ls)-len(ls))%2:
    ret = 1
  else:
    ret = 2
  return ret
if n%2 == 0:
  if sum(a)%2:
    print("First")
  else:
    print("Second")
else:
  cnt = 0
  while flg(a)%2 == 0:
    odd = 0
    oddidx = -1
    even = 0
    for i,x in enumerate(a):
      if x%2:
        odd += 1
        oddidx = i
      else:
        even += 1
    if odd == 1 and a[oddidx] > 1:
      a[oddidx] -= 1
      g = gcds(a)
      for i in range(n):
        a[i] //= g
      cnt += 1
    else:
      break
  if (flg(a)+cnt)%2 == 1:
    print("First")
  else:
    print("Second")

Solution (Python):
import sys
readline = sys.stdin.readline
from functools import reduce
def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

def calc(A):
    N = len(A)
    if N == 1:
        return A[0]%2 == 0

    K = sum(1 for a in A if a % 2 == 0)
    if K & 1:
        return True
    if N-K != 1:
        return False
    if min(A) == 1:
        return False
    A = [a-a%2 for a in A]
    g = reduce(gcd, A)
    A = [a//g for a in A]
    return not calc(A)


N = int(readline())
A = list(map(int, readline().split()))
print('First' if calc(A) else 'Second')

Solution (Python):





from fractions import gcd

def count(a):
    odd, even = 0,0
    for x in a:
        if x % 2 == 1: odd = odd + 1
        else: even = even + 1
    return odd,even

def deal(n,a):
    odd,even = count(a)
    if even == 0:
        return False
    if even % 2 == 1:
        return True
    if odd > 1:
        return False
    
    
    
    
    if a[0] % 2 == 0:
        g = a[0]
    else:
        g = a[1]
        
    for i in range(0,n):
        if a[i] % 2 == 1:
            if a[i] == 1: 
                return False
            a[i]  -= 1
        g = gcd(a[i], g)
    return not deal(n,list(map(lambda x: x//g,a)))

n = int(input())
a = [int(i) for i in input().split()]
if deal(n,a):
    print('First')
else:
    print('Second')

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def gcd_list(A):
    res = A[0]
    for a in A:
        res = gcd(a, res)
    return res

def check(N,A):
    if 1 in A:
        if((sum(A)-N) & 1):
            return 0 
        else:
            return 1 
    odd_cnt, even_cnt = 0, 0
    for a in A:
        if(a&1):
            odd_cnt += 1
        else:
            even_cnt += 1
    if(even_cnt & 1):
        return 0
    else:
        if(odd_cnt >= 2):
            return 1
        else: 
            odd_idx = [i for i in range(N) if A[i]&1 ][0]
            A[odd_idx] -= 1
            G = gcd_list(A)
            return check(N, [a//G for a in A]) ^ 1
def main():
    N=I()
    A=LI()
    print(["First","Second"][check(N,A)])



if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

import numpy as np

N = int(readline())
A = np.array([int(x) for x in readline().split()])

if N == 1:
    print('Second')
    exit()


def gcd(A):
    B = A.copy()
    while len(B) > 1:
        i = np.argmin(B)
        d = B[i]
        B %= d
        B[i] = d
        B = B[B!=0]
    return B[0]

def can_win(A):
    od = (A&1).sum()
    ev = N-od
    if ev % 2 == 1:
        
        return True
    if od > 1:
        
        return False
    i = np.where(A&1)[0][0]
    if A[i] == 1:
        
        return False
    
    A[i] -= 1
    d = gcd(A)
    A //= d
    return not(can_win(A))

answer = 'First' if can_win(A) else 'Second'
print(answer)

Solution (Python):
from fractions import gcd
 
def gcdL(L):
    g=L[0]
    for i in range(1,len(L)):
        if g==1:
            return(g)
        g=gcd(g,L[i])
    return g
def play(A,i):
    A[i]-=1
    g=gcdL(A)
    return [x//g for x in A]
def cnt(A):
    odd,even=0,0
    for a in A:
        if a%2:
            odd+=1
        else:
            even+=1
    return odd,even    

n=int(input())
A=list(map(int,input().split()))
First=1
while True:
    odd,even=cnt(A)
    if even%2:
        print('First' if First else 'Second')
        break
    elif odd>1:
        print('Second' if First else 'First')
        break
    else:
        for i in range(n):
            if A[i]%2:
                break
        if A[i]==1:
            print('Second' if First else 'First')
            break
        else:
            A=play(A,i)
            First^=1

Solution (Python):
from fractions import gcd
 
def gcdL(L):
    g=L[0]
    for i in range(1,len(L)):
        if g==1:
            return(g)
        g=gcd(g,L[i])
    return g
def play(A,i):
    A[i]-=1
    g=gcdL(A)
    return [x//g for x in A]
def cnt(A):
    odd,even=0,0
    for a in A:
        if a%2:
            odd+=1
        else:
            even+=1
    return odd,even    

n=int(input())
A=list(map(int,input().split()))
First=1
while True:
    odd,even=cnt(A)
    if even%2:
        print('First' if First else 'Second')
        break
    elif odd>1:
        print('Second' if First else 'First')
        break
    else:
        for i in range(n):
            if A[i]%2:
                break
        if A[i]==1:
            print('Second' if First else 'First')
            break
        else:
            A=play(A,i)
            First^=1

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
S=sum(A)
def gcd(x,y):
  if x<y:
    x,y=y,x
  if x%y==0:
    return y
  return gcd(y,x%y)
if (S-N)%2:
  print("First")
else:
  First=False
  while True:
    odd=-1
    for i in range(N):
      if A[i]%2:
        if odd>=0 or A[i]==1:
          if First:
            print("First")
          else:
            print("Second")
          exit()
        A[i]-=1
        odd=i
      if i==0:
        g=A[0]
      else:
        g=gcd(g,A[i])
    S=0
    for i in range(N):
      A[i]=A[i]//g
      S+=A[i]
    if (S-N)%2==0:
      if First:
        First=False
      else:
        First=True
    else:
      if First:
        print("First")
      else:
        print("Second")
      exit()

Solution (Python):
import random
def tester(N=0):
	'''制約
1≦N≦105
1≦Ai≦109
'''
	maxno1=1e5
	maxno2=1e9
	s=input()
	if s!='':return(s)
	
	if N==0:
		return(random.randint(2,maxno1))
	else:
		print('Testing...')
		print('N=',N)
		A=[]
		for i in range(N):
			A.extend([random.randint(1,maxno2)])
		return(' '.join(list(map(str,A))))

import copy

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def gcdm(x):
	g=x[0]
	for i in range(1,len(x)):
		if g==1:
			return(g)
		g=gcd(g,x[i])
	return(g)

def playmove(A,i):
	A[i]-=1
	g=gcdm(A)
	return([x//g for x in A])

def noofevens(A):
	r=0
	for i in A:
		if i%2==0:
			r+=1
	return(r)
			

N=int(tester())
A=[int(x) for x in tester(N).split()]


isFirstmove=True
while True:
	e=noofevens(A)
	if e%2==1:
		if isFirstmove:
			print('First')
		else:
			print('Second')
		break
	elif N-e>1:
		if isFirstmove:
			print('Second')
		else:
			print('First')
		break
	else:	
		for i in range(N):
			if A[i]%2==1:
				break
		if A[i]==1:
			if isFirstmove:
				print('Second')
			else:
				print('First')
			break
		else:
			A=playmove(A,i)
			isFirstmove=(isFirstmove!=True)

Solution (Python):



from fractions import gcd

def readln(ch):
    _res = list(map(int,str(input()).split(ch)))
    return _res

def count(a):
    odd, even = 0,0
    for x in a:
        if x % 2 == 1: odd = odd + 1
        else: even = even + 1
    return odd,even

def deal(n,a):
    odd,even = count(a)
    if even == 0:
        return False
    if even % 2 == 1:
        return True
    if odd > 1:
        return False
    if a[0] % 2 == 0:
        res = a[0]
    else:
        res = a[1]
    for i in range(0,n):
        if a[i] % 2 == 1:
            if a[i] == 1: return False
            a[i] = a[i] - 1
        res = gcd(a[i],res)
    return not deal(n,list(map(lambda x: x//res,a)))

n = int(input())
a = readln(' ')
if deal(n,a):
    print('First')
else:
    print('Second')

Solution (Python):
from fractions import gcd
def solve(a):
    n = len(a)
    s = [(x + 1) & 1 for x in a]
    ss = sum(s)
    if ss == n:
        a[0] -= 1
    elif ss == n - 1:
        for i in xrange(n):
            if s[i] == 0 and a[i] > 1:
                a[i] -= 1
                break
        else:
            return ss & 1
    else:
        return ss & 1
    g = reduce(gcd, a)
    return not solve([x / g for x in a])

def main():
    n = int(raw_input())
    a = map(int, raw_input().split())
    print "First" if solve(a) else "Second"
main()