Problem:


Score : 800 points

Problem Statement

You are given a polynomial of degree N with integer coefficients: f(x)=a_Nx^N+a_{N-1}x^{N-1}+...+a_0. Find all prime numbers p that divide f(x) for every integer x.

Constraints

0 \leq N \leq 10^4

|a_i| \leq 10^9(0\leq i\leq N)

a_N \neq 0

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_N
:
a_0

Output

Print all prime numbers p that divide f(x) for every integer x, in ascending order.

Sample Input 1

2
7
-7
14

Sample Output 1

2
7

2 and 7 divide, for example, f(1)=14 and f(2)=28.

Sample Input 2

3
1
4
1
5

Sample Output 2

There may be no integers that satisfy the condition.

Sample Input 3

0
998244353

Sample Output 3

998244353



Sample input:
2
7
-7
14


Sample output:
2
7

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
def k(n):
    a = []
    if n%2==0:
      a.append(2)
    while n % 2 == 0:
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            while n%f==0:
                n=n//f
        f += 2
    if n != 1:
        a.append(n)
    return a
N=int(input())
L=list()
for i in range(N+1):
  s=int(input())
  L.append(s)
ans=list(k(abs(L[-1])))
p=np.poly1d(L)
w=p(0)
for j in range(-(N//2),(N//2)+2):
  w=math.gcd(w,p(j))
  if w==1:
    break
S=k(w)
for i in S:
  print(i)

Submission status: Wrong Answer

Solution code:
def f(x):
  n=abs(x)
  r=[]
  for i in range(2,int(n**0.5)+1):
    if n%i==0:
      r.append(i)
      while n%i==0:
        n//=i
  if n!=1:
    r.append(n)
  return r

N=int(input())
A=[int(input()) for i in range(N+1)]
while A[-1]==0:
  del A[-1]
X=set(f(A[-1]))
for i in range(len(A)):
  if A[i]:
    X&=(set(f(A[i]))|{2})
print(*X,sep='\n')

Submission status: Wrong Answer

Solution code:
def factorization(n):
    a = n
    p = 2
    D = {}
    while a != 1:
        cnt = 0
        while a % p == 0:
            cnt += 1
            a //= p
        if cnt:
            D[p] = cnt
        p += 1
        if a != 1 and p * p > n:
            D[a] = 1
            break
    return D

N = int(input())
A = [0 for _ in range(N+1)]
for i in range(N+1):
    A[-i-1] = int(input())
non_zero = 0
while A[non_zero] == 0:
    non_zero += 1
num = 0
if A[non_zero] < 0:
    num = -A[non_zero]
else:
    num = A[non_zero]
F = factorization(num)
PS = sum(A)
NS = 0
for i in range(N+1):
    NS += (i%2 - (i+1)%2) * A[i]
X = []
for i in F:
    if PS % i == 0 and NS % i == 0:
        X.append(i)
X.sort()
NN = len(X)
for i in range(NN):
    print(X[i])

Submission status: Wrong Answer

Solution code:
import sys,math

def I(): return int(sys.stdin.readline().rstrip())

N = I()
a = [I() for _ in range(N+1)]
a.reverse()

ans = set([])

g = a[0]
for i in range(N):
    g = math.gcd(g,a[i+1])

for p in range(2,int(g**.5)+1):
    if g % p == 0:
        ans.add(p)
        g //= p
if g != 1:
    ans.add(g)

if N == 0:
    list(ans).sort()
    print(*ans, sep='\n')
    exit()


def sieve_of_eratosthenes(n):
    prime_list = []  # n以下の素数のリスト
    A = [1]*(n+1)    # A[i] = iが素数なら1,その他は0
    A[0] = A[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if A[i]:
            prime_list.append(i)
            for j in range(i**2,n+1,i):
                A[j] = 0
    for i in range(math.floor(math.sqrt(n))+1,n+1):
        if A[i] == 1:
            prime_list.append(i)
    return prime_list


prime_list = sieve_of_eratosthenes(N)

for p in prime_list:  # f(x) が x**p-x で割り切れるかを判定
    if a[0] % p != 0:
        continue
    else:
        for i in range(p-1):
            if i == 0:
                r = 0
                for j in range(p-1,N+1,p-1):
                    r += a[j]
                    r %= p
                if r != 0:
                    break
            else:
                r = 0
                for j in range(i,N+1,p-1):
                    r += a[j]
                    r %= p
                if r != 0:
                    break
        else:
            ans.add(p)

list(ans).sort()
print(*ans,sep='\n')

Submission status: Wrong Answer

Solution code:
def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def Ind(b,n):
    count=0
    while n%b==0:
        count+=1
        n//=b
    return count

prime=get_sieve_of_eratosthenes_new(10**4+1)

from fractions import gcd

N=int(input())
a=[]
for i in range(N+1):
    a.append(int(input()))

a=a[::-1]
ans=set([])
for p in prime:
    data=[0 for i in range(p)]
    for i in range(1,N+1):
        data[(i-1)%(p-1)]+=a[i]%p
        data[(i-1)%(p-1)]%=p
    check=(a[0]%p==0)
    for i in range(p):
        check=check&(data[i]%p==0)
    if check:
        ans.add(p)


n=a[0]
for i in range(N+1):
    n=gcd(n,a[i])

prime=get_sieve_of_eratosthenes_new(32000)

for p in prime:
    i=Ind(p,n)
    if i!=0:
        ans.add(p)
    n//=pow(p,i)

if abs(n)!=1:
    ans.add(n)

ans=list(ans)
ans.sort()
for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def Ind(b,n):
    count=0
    while n%b==0:
        count+=1
        n//=b
    return count

prime=get_sieve_of_eratosthenes_new(10**4+1)

from fractions import gcd

N=int(input())
a=[]
for i in range(N+1):
    a.append(int(input()))

a=a[::-1]
ans=set([])
for p in prime:
    data=[0 for i in range(p)]
    for i in range(1,N+1):
        data[(i-1)%(p-1)]+=a[i]%p
        data[(i-1)%(p-1)]%=p
    check=(a[0]%p==0)
    for i in range(p):
        check=check&(data[i]%p==0)
    if check:
        ans.add(p)


n=a[0]
for i in range(N+1):
    n=gcd(n,a[i])

for p in prime:
    i=Ind(p,n)
    if i!=0:
        ans.add(p)
    n//=pow(p,i)

if abs(n)!=1:
    ans.add(n)

ans=list(ans)
ans.sort()
for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def Ind(b,n):
    count=0
    while n%b==0:
        count+=1
        n//=b
    return count

prime=get_sieve_of_eratosthenes_new(10**4+1)

from fractions import gcd

N=int(input())
a=[]
for i in range(N+1):
    a.append(int(input()))

a=a[::-1]
ans=set([])
for p in prime:
    data=[0 for i in range(p)]
    for i in range(1,N+1):
        data[(i-1)%(p-1)]+=a[i]%p
        data[(i-1)%(p-1)]%=p
    check=(a[0]%p==0)
    for i in range(p):
        check=check&(data[i]%p==0)
    if check:
        ans.add(p)


n=a[0]
for i in range(N):
    n=gcd(n,a[i])

for p in prime:
    i=Ind(p,n)
    if i!=0:
        ans.add(p)
    n//=pow(p,i)

if abs(n)!=1:
    ans.add(n)

ans=list(ans)
ans.sort()
for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def Ind(b,n):
    count=0
    while n%b==0:
        count+=1
        n//=b
    return count

prime=get_sieve_of_eratosthenes_new(10**4+1)

from fractions import gcd

N=int(input())
a=[]
for i in range(N+1):
    a.append(int(input()))

a=a[::-1]
ans=set([])
for p in prime:
    data=[0 for i in range(p)]
    for i in range(1,N):
        data[(i-1)%(p-1)]+=a[i]%p
        data[(i-1)%(p-1)]%=p
    check=(a[0]%p==0)
    for i in range(p):
        check=check&(data[i]%p==0)
    if check:
        ans.add(p)


n=a[0]
for i in range(N):
    n=gcd(n,a[i])

for p in prime:
    i=Ind(p,n)
    if i!=0:
        ans.add(p)
    n//=pow(p,i)

if n!=1:
    ans.add(n)

ans=list(ans)
ans.sort()
for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def Ind(b,n):
    count=0
    while n%b==0:
        count+=1
        n//=b
    return count

prime=get_sieve_of_eratosthenes_new(10**4+1)

from fractions import gcd

N=int(input())
a=[]
for i in range(N+1):
    a.append(int(input()))

a=a[::-1]
ans=set([])
for p in prime:
    data=[0 for i in range(p)]
    for i in range(1,N):
        data[(i-1)%(p-1)]+=a[i]%p
        data[(i-1)%(p-1)]%=p
    check=(a[0]%p==0)
    for i in range(p):
        check=check&(data[i]%p==0)
    if check:
        ans.add(p)

n=a[0]
for i in range(N):
    n=gcd(n,a[0])

for p in prime:
    i=Ind(p,n)
    if i!=0:
        ans.add(p)
    n//=pow(p,i)

if n!=1:
    ans.add(n)

ans=list(ans)
ans.sort()
for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

sosuu=[2];n=int(input())
for L in range(3,n+100):
    chk=True
    for L2 in sosuu:
        if L%L2 == 0:chk=False
    if chk==True:sosuu.append(L)
S=set(sosuu)



A=[0]*(n+1)
g=0
for i in range(n+1):
  A[i]=int(input())
P=[]
PP=factorization(abs(A[0]))
for i in range(len(PP)):
  P.append(PP[i][0])
if P==[1]:
  P=[]
P=set(P)
P=S|P
P=list(P)
P.sort()
for i in range(len(P)):
  p=P[i]
  B=A[0:n+2]
  b=0
  for j in range(n+1):
    if p+j<n+2:
      B[j+p-1]=(B[j+p-1]+B[j])%p
    else:
      if B[j]%p!=0:
        b=1
        break
  if b==0:
    print(p)

Submission status: Wrong Answer

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

sosuu=[2];n=int(input())
for L in range(3,n):
    chk=True
    for L2 in sosuu:
        if L%L2 == 0:chk=False
    if chk==True:sosuu.append(L)
S=set(sosuu)




A=[0]*(n+1)
g=0
for i in range(n+1):
  A[i]=int(input())
P=[]
PP=factorization(abs(A[0]))
for i in range(len(PP)):
  P.append(PP[i][0])
if P==[1]:
  P=[]
P=set(P)
P=S|P
P=list(P)
P.sort()
for i in range(len(P)):
  p=P[i]
  B=A[0:n+2]
  b=0
  for j in range(n+1):
    if p+j<n+2:
      B[j+p-1]=(B[j+p-1]+B[j])%p
    else:
      if B[j]%p!=0:
        b=1
        break
  if b==0:
    print(p)

Submission status: Wrong Answer

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

sosuu=[2];n=int(input())
for L in range(3,n):
    chk=True
    for L2 in sosuu:
        if L%L2 == 0:chk=False
    if chk==True:sosuu.append(L)
S=set(sosuu)




A=[0]*(n+1)
g=0
for i in range(n+1):
  A[i]=int(input())
P=[]
PP=factorization(abs(A[0]))
for i in range(len(PP)):
  P.append(PP[i][0])
if P==[1]:
  P=[]
P=set(P)
P=S|P
P=list(P)
P.sort()
for i in range(len(P)):
  p=P[i]
  B=A[0:n+2]
  b=0
  for j in range(n+1):
    if p+j<n+2:
      B[j+p-1]=(B[j+p-1]+B[j])%p
    else:
      if A[j]%p!=0:
        b=1
        break
  if b==0:
    print(p)

Submission status: Wrong Answer

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

sosuu=[2];n=int(input())
for L in range(3,n):
    chk=True
    for L2 in sosuu:
        if L%L2 == 0:chk=False
    if chk==True:sosuu.append(L)
S=set(sosuu)




A=[0]*(n+1)
g=0
for i in range(n+1):
  A[i]=int(input())
P=[]
PP=factorization(abs(A[0]))
for i in range(len(PP)):
  P.append(PP[i][0])
if P==[1]:
  P=[]
P=set(P)
P=S|P
P=list(P)
P.sort()
print(P)
for i in range(len(P)):
  p=P[i]
  B=A[0:n+2]
  b=0
  for j in range(n+1):
    if p+j<n+2:
      B[j+p-1]=(B[j+p-1]+B[j])%p
    else:
      if A[j]%p!=0:
        b=1
        break
  if b==0:
    print(p)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
from fractions import gcd

N = int(input())
A = np.array([input() for _ in range(N+1)], dtype=np.int64)[::-1]

# x^p-x で割り切れる必要がある
# p > Nのときは、a_Nの約数でなければならない
# a_Nの素因数および、N以下の素数をテストすればよい

U = int(10 ** 4.5 + 10)
is_prime = np.zeros(U+1, dtype = np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(U+1):
    if p*p > U:
        break
    if is_prime[p]:
        is_prime[p*p::2*p] = 0
primes = is_prime.nonzero()[0]

div = primes[A[N] % primes == 0]

cand = list(div)
x = abs(A[N])
for p in cand:
    while x % p == 0:
        x //= p
if x != 1:
    cand.append(x)

cand += primes[primes <= N].tolist()

def test(p):
    if A[0] % p != 0:
        return False
    # x^{p-1} - 1で割り切れるかどうか
    if p > N+10:
        return (A % p == 0).all()
    B = np.pad(A,[0,(-N-1)%(p-1)],'constant').reshape(-1,p-1).sum(axis = 0)
    return (B % p == 0).all()

cand.sort()
answer = '\n'.join(str(p) for p in cand if test(p))
print(answer)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(reversed([int(input()) for i in range(n+1) ]))

prime = [2,3]

for i in range(5,100000):
    f = True
    for p in prime:
        if(p*p > i):break
        if i % p == 0 :
            f = False
            break
    if f :prime.append(i)

def gcd(x,y):
    if(x < y): x,y = y,x
    if(y == 0): return x
    return gcd(y,x % y)

def isprime(x):
    f = True
    for p in prime:
        if(p*p > x):break
        if x % p == 0:
            f = False
            break
    return f

g = 0
for i in a:
    g = gcd(abs(i),g)



for p in prime:
    if (p > n+1):break
    m = [0 for i in range(p-1)]
    if a[0] % p != 0:continue
    for i in range(n+1):
        m[i % (p-1)] += (a[i] % p)
    f = True
    for i in m:
        if i % p > 0 :
            f = False
            break    
    if f:print(p)




for p in prime:
    if g == 1:break
    if(g % p == 0):
        g //= p
        if (p > n):print(p)

if(g != 1):
    if isprime(g):print(g)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(reversed([int(input()) for i in range(n+1) ]))

prime = [2,3]

for i in range(5,100000):
    f = True
    for p in prime:
        if(p*p > i):break
        if i % p == 0 :
            f = False
            break
    if f :prime.append(i)

def gcd(x,y):
    if(x < y): x,y = y,x
    if(y == 0): return x
    return gcd(y,x % y)

def isprime(x):
    f = True
    for p in prime:
        if(p*p > x):break
        if x % p == 0:
            f = False
            break
    return f

g = 0
for i in a:
    g = gcd(abs(i),g)



for p in prime:
    if (p > n+1):break
    m = [0 for i in range(p-1)]
    for i in range(n+1):
        m[i % (p-1)] += (a[i] % p)
    f = True
    for i in m:
        if i % p > 0 :
            f = False
            break    
    if f:print(p)




for p in prime:
    if g == 1:break
    if(g % p == 0):
        g //= p
        if (p > n+1):print(p)

if(g != 1):
    if isprime(g):print(g)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(reversed([int(input()) for i in range(n+1) ]))

prime = [2,3]

for i in range(5,100000):
    f = True
    for p in prime:
        if(p*p > i):break
        if i % p == 0 :
            f = False
            break
    if f :prime.append(i)

def gcd(x,y):
    if(x < y): x,y = y,x
    if(y == 0): return x
    return gcd(y,x % y)

def isprime(x):
    f = True
    for p in prime:
        if(p*p > x):break
        if x % p == 0:
            f = False
            break
    return f

g = 0
for i in a:
    g = gcd(abs(i),g)



for p in prime:
    if (p > n+1):break
    m = [0 for i in range(p-1)]
    for i in range(n+1):
        m[i % (p-1)] += (a[i] % p)
    f = True
    for i in m:
        if i % p > 0 :
            f = False
            break    
    if f:print(p)




for p in prime:
    if g == 1:break
    if(g % p == 0):
        g //= p
        if (p > n):print(p)

if(g != 1):
    if isprime(g):print(g)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(reversed([int(input()) for i in range(n+1) ]))

prime = [2,3]

for i in range(5,100000):
    f = True
    for p in prime:
        if(p*p > i):break
        if i % p == 0 :
            f = False
            break
    if f :prime.append(i)

def gcd(x,y):
    if(x < y): x,y = y,x
    if(y == 0): return x
    return gcd(y,x % y)

def isprime(x):
    f = True
    for p in prime:
        if(p*p > x):break
        if x % p == 0:
            f = False
            break
    return f

g = 0
for i in a:
    g = gcd(abs(i),g)



for p in prime:
    if (p > n):break
    m = [0 for i in range(p-1)]
    for i in range(n+1):
        m[i % (p-1)] += (a[i] % p)
    f = True
    for i in m:
        if i % p > 0 :
            f = False
            break    
    if f:print(p)




for p in prime:
    if g == 1:break
    if(g % p == 0):
        g //= p
        if (p > n):print(p)

if(g != 1):
    if isprime(g):print(g)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(reversed([int(input()) for i in range(n+1) ]))

prime = [2,3]

for i in range(5,100000):
    f = True
    for p in prime:
        if(p*p > i):break
        if i % p == 0 :
            f = False
            break
    if f :prime.append(i)

def gcd(x,y):
    if(x < y): x,y = y,x
    if(y == 0): return x
    return gcd(y,x % y)

def isprime(x):
    f = True
    for p in prime:
        if x % p == 0:
            f = False
            break
    return f

g = 0
for i in a:
    g = gcd(abs(i),g)



for p in prime:
    if (p > n):break
    m = [0 for i in range(p-1)]
    for i in range(n+1):
        m[i % (p-1)] += (a[i] % p)
    f = True
    for i in m:
        if i % p > 0 :
            f = False
            break    
    if f:print(p)




for p in prime:
    if g == 1:break
    if(g % p == 0):
        g //= p
        if (p > n):print(p)

if(g != 1):
    if isprime(g):print(g)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
n = int(input())
a = [int(input()) for _ in range(n+1)]
x = 0
while True:
	m = abs(sum([a[i]*pow(x, n-i) for i in range(n+1)]))
	if m != 0:
		break
	x += 1
ps = []

i = 2
while i**2 <= m and i <= n+1:
#for i in range(2, int(sqrt(m))+1):
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
	i += 1

g = a[0]
for i in range(1, n+1):
	g = gcd(g, abs(a[i]))

#print(g)
ans = []

i = 2
while i**2 <= g:
#for i in range(2, int(sqrt(m))+1):
	if g%i == 0:
		if i >= n+1:
			ans.append(i)
		while g%i == 0:
			g //= i
	i += 1
if g != 1 and g >= n+1:
	ans.append(g)

a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			ans.append(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				ans.append(p)
ans = sorted(list(set(ans)))
if ans:
	print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
n = int(input())
a = [int(input()) for _ in range(n+1)]
x = 0
while True:
	m = abs(sum([a[i]*pow(x, n-i) for i in range(n+1)]))
	if m != 0:
		break
	x += 1
ps = []

i = 2
while i**2 <= m and i <= n+1:
#for i in range(2, int(sqrt(m))+1):
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
	i += 1
if m != 1:
	ps.append(m)

g = a[0]
for i in range(1, n+1):
	g = gcd(g, abs(a[i]))

#print(g)
ans = []

i = 2
while i**2 <= g:
#for i in range(2, int(sqrt(m))+1):
	if g%i == 0:
		if i >= n+1:
			ans.append(i)
		while g%i == 0:
			g //= i
	i += 1
if g != 1 and g >= n+1:
	ans.append(g)

a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			ans.append(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				ans.append(p)
ans = sorted(list(set(ans)))
if ans:
	print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
n = int(input())
a = [int(input()) for _ in range(n+1)]
x = 0
while True:
	m = abs(sum([a[i]*pow(x, n-i) for i in range(n+1)]))
	if m != 0:
		break
	x += 1
ps = []

i = 2
while i**2 <= m and i <= n+1:
#for i in range(2, int(sqrt(m))+1):
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
	i += 1
if m != 1:
	ps.append(m)

g = a[0]
for i in range(1, n+1):
	g = gcd(g, abs(a[i]))

#print(g)
ans = []

i = 2
while i**2 <= g:
#for i in range(2, int(sqrt(m))+1):
	if g%i == 0:
		if i > n+1:
			ans.append(i)
		while g%i == 0:
			g //= i
	i += 1
if g != 1:
	ans.append(g)

a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			ans.append(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				ans.append(p)
ans = sorted(list(set(ans)))
if ans:
	print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
n = int(input())
a = [int(input()) for _ in range(n+1)]
x = 0
while True:
	m = abs(sum([a[i]*pow(x, n-i) for i in range(n+1)]))
	if m != 0:
		break
	x += 1
ps = []

i = 2
while i**2 <= m and i <= n+1:
#for i in range(2, int(sqrt(m))+1):
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
	i += 1
if m != 1 and m <= n+1:
	ps.append(m)

g = a[0]
for i in range(1, n+1):
	g = gcd(g, abs(a[i]))

#print(g)
ans = []

i = 2
while i**2 <= g:
#for i in range(2, int(sqrt(m))+1):
	if g%i == 0:
		if i > n+1:
			ans.append(i)
		while g%i == 0:
			g //= i
	i += 1
if g != 1 and g > n+1:
	ans.append(g)

a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			ans.append(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				ans.append(p)
ans = sorted(list(set(ans)))
if ans:
	print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
n = int(input())
a = [int(input()) for _ in range(n+1)]
x = 0
while True:
	m = abs(sum([a[i]*pow(x, n-i) for i in range(n+1)]))
	if m != 0:
		break
	x += 1
ps = []

i = 2
while i**2 <= m and i <= n+1:
#for i in range(2, int(sqrt(m))+1):
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
	i += 1
#if m != 1:
	#ps.append(m)

g = a[0]
for i in range(1, n+1):
	g = gcd(g, abs(a[i]))

#print(g)
ans = []

i = 2
while i**2 <= g:
#for i in range(2, int(sqrt(m))+1):
	if g%i == 0:
		if i > n+1:
			ans.append(i)
		while g%i == 0:
			g //= i
	i += 1
if g != 1 and g > n+1:
	ans.append(g)

#if n == 0:
#	if ps:
#		print(*ps, sep="\n")
#	sys.exit()
a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			ans.append(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				ans.append(p)
ans = sorted(list(set(ans)))
if ans:
	print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
n = int(input())
a = [int(input()) for _ in range(n+1)]
x = 0
while True:
	m = abs(sum([a[i]*pow(x, n-i) for i in range(n+1)]))
	if m != 0:
		break
	x += 1
ps = []

i = 2
while i**2 <= m and i <= n+1:
#for i in range(2, int(sqrt(m))+1):
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
	i += 1
#if m != 1:
	#ps.append(m)

g = a[0]
for i in range(1, n+1):
	g = gcd(g, abs(a[i]))

#print(g)
ans = []

i = 2
while i**2 <= g:
#for i in range(2, int(sqrt(m))+1):
	if g%i == 0:
		if i > n+1:
			ans.append(i)
		while g%i == 0:
			g //= i
	i += 1
if g != 1 and g > n+1:
	ans.append(g)

a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			ans.append(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				ans.append(p)
ans.sort()
if ans:
	print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
from sys import exit
from math import sqrt
n = int(input())
a = [int(input()) for _ in range(n+1)]
#xx = [0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5, 6, -6]
x = 0
#for x in xx:
while True:
	m = abs(sum([a[i]*pow(x, n-i) for i in range(n+1)]))
	if m != 0:
		break
	x += 1

Submission status: Wrong Answer

Solution code:
from sys import exit
from math import sqrt
n = int(input())
a = [int(input()) for _ in range(n+1)]
#xx = [0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5, 6, -6]
x = 0
#for x in xx:
while True:
	m = abs(sum([a[i]*pow(x, n-i) for i in range(n+1)]))
	if m != 0:
		break

Submission status: Wrong Answer

Solution code:
from sys import exit
from math import sqrt
n = int(input())
a = [int(input()) for _ in range(n+1)]
xx = [0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5, 6, -6]
for x in xx:
	m = abs(sum([a[i]*pow(x, n-i) for i in range(n+1)]))
	if m != 0:
		break

Submission status: Wrong Answer

Solution code:
from sys import exit
from math import sqrt
n = int(input())
a = [int(input()) for _ in range(n+1)]
for i in range(n, -1, -1):
	if a[i] != 0:
		a = a[:i+1]
		n = i
		break
#print(a, n)
m = abs(a[n])
ans, ps = [], []
for i in range(2, int(sqrt(m))+1):
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
if m != 1:
	ps.append(m)
if n == 0:
	if ps:
		print(*ps, sep="\n")
	exit()
a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			print(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				print(p)

Submission status: Wrong Answer

Solution code:
from sys import exit
from math import sqrt
n = int(input())
a = [int(input()) for _ in range(n+1)]
for i in range(n, -1, -1):
	if a[i] != 0:
		a = a[:i+1]
		n = i
		break
#print(a, n)
m = abs(a[n])
ans, ps = [], []
for i in range(2, int(sqrt(m))+1):
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
if m != 1:
	ps.append(m)
if n == 0 and ps:
	print(*ps, sep="\n")
	exit()
a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			print(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				print(p)

Submission status: Wrong Answer

Solution code:
from sys import exit
from math import sqrt
n = int(input())
a = [int(input()) for _ in range(n+1)]
for i in range(n, -1, -1):
	if a[i] != 0:
		a = a[:i+1]
		n = i
		break
#print(a, n)
m = abs(a[n])
ans, ps = [], []
for i in range(2, int(sqrt(m))+1):
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
if m != 1:
	ps.append(m)
if n == 0 and ps:
	print(*ps, sep="\n")
	exit()
a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			print(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				print(p)
		elif mods[0] == 1:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 1:
					ng = True
					break
			if not ng:
				print(p)

Submission status: Wrong Answer

Solution code:
from sys import exit
from math import sqrt
n = int(input())
a = [int(input()) for _ in range(n+1)]
for i in range(n, -1, -1):
	if a[i] != 0:
		a = a[:i+1]
		n = i
		break
#print(a, n)
m = abs(a[n])
ans, ps = [], []
for i in range(2, int(sqrt(m))+1):
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
if m != 1:
	ps.append(m)
if n == 0:
	print(*ps, sep="\n")
	exit()
a = a[::-1]
for p in ps:
	if p-1 > n:
		ng = False
		for i in range(1, n+1):
			if a[i]%p != 0:
				ng = True
				break
		if not ng:
			print(p)
	else:
		mods = [0 for _ in range(p-1)]
		for i in range(1, n+1):
			mods[i%(p-1)] += a[i]
			mods[i%(p-1)] %= p
		if mods[0] == 0:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 0:
					ng = True
					break
			if not ng:
				print(p)
		elif mods[0] == 1:
			ng = False
			for i in range(1, p-1):
				if mods[i] != 1:
					ng = True
					break
			if not ng:
				print(p)