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:
def factors(z):
    ret = []
    for i in range(2, int(z**(1/2))+1):
        if z%i == 0:
            ret.append(i)
            while z%i == 0:
                z //= i
    if z != 1:
        ret.append(z)
    return ret
N = int( input())
A = [ int( input()) for _ in range(N+1)]
for i in range(N,-1,-1):
    if A[i] != 0:
        Primes = factors(abs(A[i]))
        break
ANS = []
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1):
            if A[i]%p != 0:
                check = 0
                break
        if check == 1:
            ANS.append(p)
    else:
        poly = [0]*(p-1)
        for i in range(N+1):
            poly[(N-i)%(p-1)] = (poly[(N-i)%(p-1)] + A[i])%p
        check = 1
        if sum(poly) != 0:
            check = 0
        # if sum(poly[1:]) != 0 or poly[1] != 0:
        #     check = 0
        # if sum(poly) == 0:
        #     check = 1
    # if poly[0] != p-1 or poly[p-1] != 1:
    #     check = 0
    # for i in range(1, p-1):
    #     if poly[i] != 0:
    #         check = 0
    # if p == 2:
    #     if A[N]%2 == 0 and sum(A)%2 == 0:
    #         check = 1
    # if sum(poly) == 0:
    #     check = 1
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

Submission status: Wrong Answer

Solution code:
def factors(z):
    ret = []
    for i in range(2, int(z**(1/2))+1):
        if z%i == 0:
            ret.append(i)
            while z%i == 0:
                z //= i
    if z != 1:
        ret.append(z)
    return ret
N = int( input())
A = [ int( input()) for _ in range(N+1)]
for i in range(N,-1,-1):
    if A[i] != 0:
        Primes = factors(abs(A[i]))
        break
ANS = []
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1):
            if A[i]%p != 0:
                check = 0
                break
        if check == 1:
            ANS.append(p)
    else:
        poly = [0]*p
        for i in range(N, -1, -1):
            poly[i%(p-1)] = (poly[i%(p-1)] + A[N-i])%p
        check = 1
        if sum(poly) != 0:
            check = 0
        # if sum(poly[1:]) != 0 or poly[1] != 0:
        #     check = 0
        # if sum(poly) == 0:
        #     check = 1
    # if poly[0] != p-1 or poly[p-1] != 1:
    #     check = 0
    # for i in range(1, p-1):
    #     if poly[i] != 0:
    #         check = 0
    # if p == 2:
    #     if A[N]%2 == 0 and sum(A)%2 == 0:
    #         check = 1
    # if sum(poly) == 0:
    #     check = 1
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

Submission status: Wrong Answer

Solution code:
def factors(z):
    ret = []
    for i in range(2, int(z**(1/2))+1):
        if z%i == 0:
            ret.append(i)
            while z%i == 0:
                z //= i
    if z != 1:
        ret.append(z)
    return ret
N = int( input())
A = [ int( input()) for _ in range(N+1)]
for i in range(N,-1,-1):
    if A[i] != 0:
        Primes = factors(abs(A[i]))
        break
ANS = []
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1):
            if A[i]%p != 0:
                check = 0
                break
        if check == 1:
            ANS.append(p)
    else:
        poly = [0]*p
        for i in range(N, -1, -1):
            poly[i%(p-1)] = (poly[i%(p-1)] + A[N-i])%p
        check = 1
        if sum(poly[1:]) != 0 or poly[1] != 0:
            check = 0
        if sum(poly) == 0:
            check = 1
    # if poly[0] != p-1 or poly[p-1] != 1:
    #     check = 0
    # for i in range(1, p-1):
    #     if poly[i] != 0:
    #         check = 0
    # if p == 2:
    #     if A[N]%2 == 0 and sum(A)%2 == 0:
    #         check = 1
    # if sum(poly) == 0:
    #     check = 1
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

Submission status: Wrong Answer

Solution code:
def factors(z):
    ret = []
    for i in range(2, int(z**(1/2))+1):
        if z%i == 0:
            ret.append(i)
            while z%i == 0:
                z //= i
    if z != 1:
        ret.append(z)
    return ret
N = int( input())
A = [ int( input()) for _ in range(N+1)]
for i in range(N,-1,-1):
    if A[i] != 0:
        Primes = factors(abs(A[i]))
        break
ANS = []
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1):
            if A[i]%p != 0:
                check = 0
                break
        if check == 1:
            ANS.append(p)
    else:
        poly = [0]*p
        for i in range(N, -1, -1):
            poly[N%(p-1)] = (poly[N%(p-1)] + A[N-i])%p
        check = 1
        if sum(poly[1:]) != 0 or poly[1] != 0:
            check = 0
        if sum(poly) == 0:
            check = 1
    # if poly[0] != p-1 or poly[p-1] != 1:
    #     check = 0
    # for i in range(1, p-1):
    #     if poly[i] != 0:
    #         check = 0
    # if p == 2:
    #     if A[N]%2 == 0 and sum(A)%2 == 0:
    #         check = 1
    # if sum(poly) == 0:
    #     check = 1
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

Submission status: Wrong Answer

Solution code:
def factors(z):
    ret = []
    for i in range(2, int(z**(1/2))+1):
        if z%i == 0:
            ret.append(i)
            while z%i == 0:
                z //= i
    if z != 1:
        ret.append(z)
    return ret
N = int( input())
A = [ int( input()) for _ in range(N+1)]
for i in range(N,-1,-1):
    if A[i] != 0:
        Primes = factors(abs(A[i]))
        break
ANS = []
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1):
            if A[i]%p != 0:
                check = 0
                break
        if check == 1:
            ANS.append(p)
    else:
        poly = [0]*p
        for i in range(N, -1, -1):
            poly[N%(p-1)] = (poly[N%(p-1)] + A[N-i])%p
        check = 1
        if sum(poly[1:]) != 0 or poly[1] != 0:
            check = 0
    # if poly[0] != p-1 or poly[p-1] != 1:
    #     check = 0
    # for i in range(1, p-1):
    #     if poly[i] != 0:
    #         check = 0
    # if p == 2:
    #     if A[N]%2 == 0 and sum(A)%2 == 0:
    #         check = 1
    # if sum(poly) == 0:
    #     check = 1
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

Submission status: Wrong Answer

Solution code:
def factors(z):
    ret = []
    for i in range(2, int(z**(1/2))+1):
        if z%i == 0:
            ret.append(i)
            while z%i == 0:
                z //= i
    if z != 1:
        ret.append(z)
    return ret
N = int( input())
A = [ int( input()) for _ in range(N+1)]
for i in range(N,-1,-1):
    if A[i] != 0:
        Primes = factors(abs(A[i]))
        break
ANS = []
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1):
            if A[i]%p != 0:
                check = 0
                break
        if check == 1:
            ANS.append(p)
    else:
        poly = [0]*p
        for i in range(N, -1, -1):
            poly[N%(p-1)] = (poly[N%(p-1)] + A[N-i])%p
        check = 1
        if sum(poly) != 0:
            check = 0
    # if poly[0] != p-1 or poly[p-1] != 1:
    #     check = 0
    # for i in range(1, p-1):
    #     if poly[i] != 0:
    #         check = 0
    # if p == 2:
    #     if A[N]%2 == 0 and sum(A)%2 == 0:
    #         check = 1
    # if sum(poly) == 0:
    #     check = 1
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
import math
import sys

N = int(input())
a = [int(input()) for _ in range(N + 1)]

if N == 0:
    g = a[0]
else:
    g = fractions.gcd(a[0], a[1])
    for i in range(2, N):
        g = fractions.gcd(g, a[i])
if g < 0:
    g = -g

if g % 2 == 0:
    print(2)
else:
    if a[-1] % 2 == 0 and sum(a) % 2 == 0:
        print(2)
    if g == 1:
        sys.exit(0)

bmax = int(math.sqrt(g)) + 1

b = [0] * (bmax + 1)
for i in range(4, bmax + 1, 2):
    b[i] = 1

flag = True
for i in range(3, bmax):
    if b[i] == 0:
        x = 2 * i
        while x < bmax:
            b[x] = 1
            x += i
        if g % i == 0:
            flag = False
            print(i)

if flag:
    print(g)

Submission status: Wrong Answer

Solution code:
from math import sqrt

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a%b
    return b

def divisor(a):
    lim = int(sqrt(a))
    divset = set()
    for i in range(1, lim + 1):
        if a % i == 0:
            divset |= {i, a//i}
    divset.remove(1)
    return divset

def is_prime(a):
    if a == 1: return False
    if a == 2 or a == 3: return True
    lim = int(sqrt(a))
    for i in range(2, lim + 1):
        if a % i == 0: return False
    else: return True

N = int(input())
A = [None] * (N+1)
for i in reversed(range(N+1)):
    A[i] = int(input())

primes = [int(i) for i in range(2, N)]
primes = set(primes)
for i in range(2, N):
    temp = set()
    for p in primes:
        if p % i > 0 or p == i: temp |= {p}
    primes = temp

ans = []
used = set()
for p in primes:
    for i in range(p-1):
        coefficient = 0
        index_a = i
        while index_a <= N:
            coefficient += A[index_a]
            coefficient %= p
            index_a += p-1
        if coefficient % p > 0: break
    else: 
        ans.append(p)
        used |= {p}
        
gcd_of_A = abs(A[N])
for a in A[:N]:
    if a != 0: gcd_of_A = gcd(abs(a), gcd_of_A)

commondiv = divisor(gcd_of_A)
for d in commondiv:
    if d > 1 and is_prime(d) and d not in used: ans.append(d)

ans.sort()
for a in ans: print(a)

Submission status: Wrong Answer

Solution code:
from math import sqrt

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a%b
    return b

def divisor(a):
    lim = int(sqrt(a))
    divset = set()
    for i in range(1, lim + 1):
        if a % i == 0:
            divset |= {i, a//i}
    divset.remove(1)
    return divset

def is_prime(a):
    if a == 1: return False
    if a == 2 or a == 3: return True
    lim = int(sqrt(a))
    for i in range(2, lim + 1):
        if a % i == 0: return False
    else: return True

N = int(input())
A = [None] * (N+1)
for i in reversed(range(N+1)):
    A[i] = int(input())

primes = [int(i) for i in range(2, N+1)]
primes = set(primes)
for i in range(2, N+1):
    temp = set()
    for p in primes:
        if p % i > 0 or p == i: temp |= {p}
    primes = temp

ans = []
used = set()
for p in primes:
    for i in range(p-1):
        coefficient = 0
        index_a = i
        while index_a <= N:
            coefficient += A[index_a]
            coefficient %= p
            index_a += p-1
        if coefficient % p > 0: break
    else: 
        ans.append(p)
        used |= {p}
        
gcd_of_A = abs(A[N])
for a in A[:N]:
    if a != 0: gcd_of_A = gcd(abs(a), gcd_of_A)

commondiv = divisor(gcd_of_A)
for d in commondiv:
    if d > 1 and is_prime(d) and d not in used: ans.append(d)

ans.sort()
for a in ans: print(a)

Submission status: Wrong Answer

Solution code:
from math import sqrt

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a%b
    return b

def divisor(a):
    lim = int(sqrt(a))
    divset = set()
    for i in range(1, lim + 1):
        if a % i == 0:
            divset |= {i, a//i}
    divset.remove(1)
    return divset

def is_prime(a):
    if a == 1: return False
    if a == 2 or a == 3: return True
    lim = int(sqrt(a))
    for i in range(2, lim + 1):
        if a % i == 0: return False
    else: return True

N = int(input())
A = [None] * (N+1)
for i in reversed(range(N+1)):
    A[i] = int(input())

primes = [int(i) for i in range(2, N+1)]
primes = set(primes)
for i in range(2, N+1):
    temp = set()
    for p in primes:
        if p % i > 0 or p == i: temp |= {p}
    primes = temp

ans = []
for p in primes:
    for i in range(p-1):
        coefficient = 0
        index_a = i
        while index_a <= N:
            coefficient += A[index_a]
            coefficient %= p
            index_a += p-1
        if coefficient % p > 0: break
    else: 
        ans.append(p)
        
gcd_of_A = abs(A[N])
for a in A[:N]:
    if a != 0: gcd_of_A = gcd(abs(a), gcd_of_A)

commondiv = divisor(gcd_of_A)
for d in commondiv:
    if d >= N and is_prime(d): ans.append(d)

ans.sort()
for a in ans: print(a)

Submission status: Wrong Answer

Solution code:
from math import sqrt

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a%b
    return b

def divisor(a):
    lim = int(sqrt(a))
    divset = set()
    for i in range(1, lim + 1):
        if a % i == 0:
            divset |= {i, a//i}
    divset.remove(1)
    return divset

def is_prime(a):
    lim = int(sqrt(a))
    for i in range(2, lim + 1):
        if a != i and a % i == 0: return False
    else: return True

N = int(input())
A = [None] * (N+1)
for i in reversed(range(N+1)):
    A[i] = int(input())

primes = [int(i) for i in range(2, N+1)]
primes = set(primes)
for i in range(2, N+1):
    temp = set()
    for p in primes:
        if p % i > 0 or p == i: temp |= {p}
    primes = temp

ans = []
for p in primes:
    for i in range(p-1):
        coefficient = 0
        index_a = i
        while index_a <= N:
            coefficient += A[index_a] % p
            coefficient %= p
            index_a += p-1
        if coefficient % p > 0: break
    else: 
        ans.append(p)

        
gcd_of_A = abs(A[N])
for a in A[:N]:
    if a != 0: gcd_of_A = gcd(abs(a), gcd_of_A)

commondiv = divisor(gcd_of_A)
for d in commondiv:
    if d >= N and is_prime(d): ans.append(d)

ans.sort()
for a in ans: print(a)

Submission status: Wrong Answer

Solution code:
from math import sqrt

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a%b
    return b

def divisor(a):
    lim = int(sqrt(a))
    divset = set()
    for i in range(1, lim + 1):
        if a % i == 0:
            divset |= {i, a//i}
    divset.remove(1)
    return divset

def is_prime(a):
    lim = int(sqrt(a))
    for i in range(2, lim + 1):
        if a != i and a % i == 0: return False
    else: return True

N = int(input())
A = [None] * (N+1)
for i in reversed(range(N+1)):
    A[i] = int(input())

primes = [int(i) for i in range(2, N+1)]
primes = set(primes)
for i in range(2, N+1):
    temp = set()
    for p in primes:
        if p % i > 0 or p == i: temp |= {p}
    primes = temp

ans = []
used = set()
for p in primes:
    for i in range(p-1):
        coefficient = 0
        index_a = i
        while index_a <= N:
            coefficient += A[index_a] % p
            coefficient %= p
            index_a += p-1
        if coefficient % p > 0: break
    else: 
        ans.append(p)
        used |= {p}
        
gcd_of_A = abs(A[N])
for a in A[:N]:
    if a != 0: gcd_of_A = gcd(abs(a), gcd_of_A)

commondiv = divisor(gcd_of_A)
for d in commondiv:
    if is_prime(d) and d not in used: ans.append(d)

ans.sort()
for a in ans: print(a)

Submission status: Wrong Answer

Solution code:
from math import sqrt

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a%b
    return b

def divisor(a):
    lim = int(sqrt(a))
    divset = set()
    for i in range(1, lim + 1):
        if a % i == 0:
            divset |= {i, a//i}
    divset.remove(1)
    return divset

def is_prime(a):
    lim = int(sqrt(a))
    for i in range(2, lim + 1):
        if a != i and a % i == 0: return False
    else: return True

N = int(input())
A = [None] * (N+1)
for i in reversed(range(N+1)):
    A[i] = int(input())

primes = [int(i) for i in range(2, N+1)]
primes = set(primes)
for i in range(2, N+1):
    temp = set()
    for p in primes:
        if p % i > 0 or p == i: temp |= {p}
    primes = temp

ans = []
for p in primes:
    for i in range(p-1):
        coefficient = 0
        index_a = i
        while index_a <= N:
            coefficient += A[index_a] % p
            coefficient %= p
            index_a += p-1
        if coefficient % p > 0: break
    else: ans.append(p)
        
gcd_of_A = abs(A[N])
for a in A[:N]:
    if a != 0: gcd_of_A = gcd(abs(a), gcd_of_A)

commondiv = divisor(gcd_of_A)
for d in commondiv:
    if d > N and is_prime(d): ans.append(d)

ans.sort()
for a in ans: print(a)

Submission status: Wrong Answer

Solution code:
import math
from fractions import gcd
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)


def isprime(x):
    q = int(math.sqrt(x))  # int() rounds to zero
    for i in range(2,q+1):   # upto q
        if x%i == 0:
            return False
    return True

def prime_division(x):
    q = int(math.sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

n = inn()
a = [0] * (n+1)
for i in range(n+1):
    a[n-i] = inn()
ddprint(a)
g = a[n]
for i in range(n):
    g = gcd(g, a[i])
p = prime_division(abs(g))
b = []
for x in p:
    if x[0] != 1:
        b.append(x[0])
ddprint("b:")
ddprint(b)

v1 = sum(a)
vm1 = sum([a[i]*(-1 if i%2==1 else 1) for i in range(n+1)])
if a[0] != 0 or v1 != 0 or vm1 != 0:
    p = a[0] if a[0] != 0 else v1 if v1 != 0 else vm1
    p0 = prime_division(abs(p))
    ps = [x[0] for x in p0 if x[0]<16000]
else:
    ps = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157]
ddprint("ps:")
ddprint(ps)
for p in ps:
    if p in b:
        continue
    ok = True
    for r in range(1,p):
        v = a[0]
        r2i = 1
        for i in range(1,n+1):
            r2i = (r2i * r) % p
            v = (v + a[i] * r2i) % p
        if v != 0:
            ok = False
            break
    if ok:
        b.append(p)

b.sort()
for x in b:
    print(x)

Submission status: Wrong Answer

Solution code:
import math
from fractions import gcd
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)


def isprime(x):
    q = int(math.sqrt(x))  # int() rounds to zero
    for i in range(2,q+1):   # upto q
        if x%i == 0:
            return False
    return True

def prime_division(x):
    q = int(math.sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

n = inn()
a = [0] * (n+1)
for i in range(n+1):
    a[n-i] = inn()
ddprint(a)
g = a[n]
for i in range(n):
    g = gcd(g, a[i])
p = prime_division(abs(g))
b = []
for x in p:
    if x[0] != 1:
        b.append(x[0])
ddprint("b:")
ddprint(b)

if a[0] != 0:
    p0 = prime_division(abs(a[0]))
    ps = [x[0] for x in p0 if x[0]<16000]
else:
    ps = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157]
ddprint("ps:")
ddprint(ps)
for p in ps:
    if p in b:
        continue
    ok = True
    for r in range(1,p):
        v = a[0]
        r2i = 1
        for i in range(1,n+1):
            r2i = (r2i * r) % p
            v = (v + a[i] * r2i) % p
        if v != 0:
            ok = False
            break
    if ok:
        b.append(p)

b.sort()
for x in b:
    print(x)

Submission status: Wrong Answer

Solution code:
import math
from fractions import gcd
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)


def isprime(x):
    q = int(math.sqrt(x))  # int() rounds to zero
    for i in range(2,q+1):   # upto q
        if x%i == 0:
            return False
    return True

def prime_division(x):
    q = int(math.sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

n = inn()
a = [0] * (n+1)
for i in range(n+1):
    a[n-i] = inn()
ddprint(a)
g = a[n]
for i in range(n):
    g = gcd(g, a[i])
p = prime_division(abs(g))
b = []
for x in p:
    if x[0] != 1:
        b.append(x[0])
ddprint("b:")
ddprint(b)

if a[0] != 0:
    p0 = prime_division(abs(a[0]))
    ps = [x[0] for x in p0 if x[0]<1600]
else:
    ps = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157]
ddprint("ps:")
ddprint(ps)
for p in ps:
    if p in b:
        continue
    ok = True
    for r in range(1,p):
        v = a[0]
        r2i = 1
        for i in range(1,n+1):
            r2i = (r2i * r) % p
            v = (v + a[i] * r2i) % p
        if v != 0:
            ok = False
            break
    if ok:
        b.append(p)

b.sort()
for x in b:
    print(x)

Submission status: Wrong Answer

Solution code:
import math
from fractions import gcd
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)


def isprime(x):
    q = int(math.sqrt(x))  # int() rounds to zero
    for i in range(2,q+1):   # upto q
        if x%i == 0:
            return False
    return True

def prime_division(x):
    q = int(math.sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

n = inn()
a = [0] * (n+1)
for i in range(n+1):
    a[n-i] = inn()
ddprint(a)
g = a[n]
for i in range(n):
    g = gcd(g, a[i])
p = prime_division(abs(g))
b = []
for x in p:
    if x[0] != 1:
        b.append(x[0])
ddprint("b:")
ddprint(b)

if a[0] != 0:
    p0 = prime_division(abs(a[0]))
    ps = [x[0] for x in p0 if x[0]<160]
else:
    ps = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157]
ddprint("ps:")
ddprint(ps)
for p in ps:
    if p in b:
        continue
    ok = True
    for r in range(1,p):
        v = a[0]
        r2i = 1
        for i in range(1,n+1):
            r2i = (r2i * r) % p
            v = (v + a[i] * r2i) % p
        if v != 0:
            ok = False
            break
    if ok:
        b.append(p)

b.sort()
for x in b:
    print(x)

Submission status: Wrong Answer

Solution code:
from math import sqrt

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a%b
    return b

def divisor(a):
    lim = int(sqrt(a))
    divset = set()
    for i in range(1, lim + 1):
        if a % i == 0:
            divset |= {i, a//i}
    divset -= {1}
    return divset

def is_prime(a):
    lim = int(sqrt(a))
    for i in range(2, lim + 1):
        if a != i and a % i == 0: return False
    else: return True

N = int(input())
A = [int(input()) for n in range(N+1)]

#gcd_of_A = A[N]
#for i in reversed(range(N)):
    #if A[i] != 0: gcd_of_A = gcd(abs(A[i]), gcd_of_A)

primes = [int(i) for i in range(2, N+1)]
primes = set(primes)
for i in range(2, N+1):
    temp = set()
    for p in primes:
        if p % i > 0 or p == i: temp |= {p}
    primes = temp

ans = []
for p in primes:
    for i in range(p-1):
        coefficient = 0
        index_a = i
        while index_a <= N:
            coefficient += A[index_a] % p
            coefficient %= p
            index_a += p-1
        if coefficient % p > 0: break
    else: 
        ans.append(p)
        
#if gcd_of_A > 1:
    #divisor_of_A = divisor(gcd_of_A)
    #for d in divisor_of_A:
        #if d > N:
            #if is_prime(d):
                #ans.append(d)

ans.sort()
for a in ans: print(a)

Submission status: Wrong Answer

Solution code:
import math
from fractions import gcd
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)


def isprime(x):
    q = int(math.sqrt(x))  # int() rounds to zero
    for i in range(2,q+1):   # upto q
        if x%i == 0:
            return False
    return True

def prime_division(x):
    q = int(math.sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

n = inn()
a = [0] * (n+1)
for i in range(n+1):
    a[n-i] = inn()
ddprint(a)
g = a[n]
for i in range(n):
    g = gcd(g, a[i])
p = prime_division(abs(g))
b = []
for x in p:
    if x[0] != 1:
        b.append(x[0])
ddprint("b:")
ddprint(b)

if a[0] != 0:
    p0 = prime_division(abs(a[0]))
    ps = [x[0] for x in p0 if x[0]<100]
else:
    ps = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
ddprint("ps:")
ddprint(ps)
for p in ps:
    if p in b:
        continue
    ok = True
    for r in range(1,p):
        v = a[0]
        r2i = 1
        for i in range(1,n+1):
            r2i = (r2i * r) % p
            v = (v + a[i] * r2i) % p
        if v != 0:
            ok = False
            break
    if ok:
        b.append(p)

b.sort()
for x in b:
    print(x)

Submission status: Wrong Answer

Solution code:
import math
from fractions import gcd
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)


def isprime(x):
    q = int(math.sqrt(x))  # int() rounds to zero
    for i in range(2,q+1):   # upto q
        if x%i == 0:
            return False
    return True

def prime_division(x):
    q = int(math.sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

n = inn()
a = [0] * (n+1)
for i in range(n+1):
    a[n-i] = inn()
ddprint(a)
g = a[n]
for i in range(n):
    g = gcd(g, a[i])
p = prime_division(abs(g))
b = []
for x in p:
    if x[0] != 1:
        b.append(x[0])
ddprint("b:")
ddprint(b)

if a[0] != 0:
    p0 = prime_division(abs(a[0]))
    ps = [x[0] for x in p0 if x[0]<50]
else:
    ps = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
ddprint("ps:")
ddprint(ps)
for p in ps:
    if p in b:
        continue
    ok = True
    for r in range(1,p):
        v = a[0]
        r2i = 1
        for i in range(1,n+1):
            r2i = (r2i * r) % p
            v = (v + a[i] * r2i) % p
        if v != 0:
            ok = False
            break
    if ok:
        b.append(p)

b.sort()
for x in b:
    print(x)

Submission status: Wrong Answer

Solution code:
def prime_fact(n: int)->list:
    '''n の素因数を返す
    '''
    if n < 2:
        return []

    d = 2
    res = []
    while n > 1 and d * d <= n:
        if n % d == 0:
            res.append(d)
        while n % d == 0:
            n //= d
        d += 1

    if n > 1:
        # n が素数
        res.append(n)

    return res


def gen_primes(n: int)->int:
    '''n まで(n 含む)の素数を返します。
    '''
    if n < 2:
        return []
    primes = [2]

    if n < 3:
        return primes
    primes.append(3)

    def is_prime(n: int)->bool:
        for p in primes:
            if n % p == 0:
                return False
        return True

    # 2,3 以降の素数は 6k+1 あるいは 6k-1
    # の形をしていることを利用して列挙する。
    for k in range((N+1)//6):
        k += 1

        if is_prime(6*k-1):
            primes.append(6*k-1)

        if is_prime(6*k+1):
            primes.append(6*k+1)

    return primes


def gcd(a: int, b: int)->int:
    if a < b:
        a, b = b, a
    return a if b == 0 else gcd(b, a % b)


def gcd_list(A: list)->int:
    if len(A) == 0:
        return 0
    if len(A) == 1:
        return A[0]

    g = A[0]
    return g


def polynominal_divisors(N: int, A: list)->list:
    # primes = prime_fact(abs(A[-1]))
    A.reverse()
    # 候補となる素数は、N 以下の素数あるいは、aN の素因数

    def check(p: int)->bool:
        '''素数 p が任意の整数 x について f(x) を割り切れるかを
        check する。具体的には、

        - a0
        - a1 + ap + a{2p-1} + ...
        - a2 + a{p+1} + a{2p} + ...
        ...
        - a{p-1} + a{2p-2} + ...
        という項が p で割り切れるかを検査する。
        '''
        if A[0] % p != 0:
            return False

        for i in range(1, min(N, p)):
            # ai + a{i+p-1} + ... を求めて
            # p で割り切れるか検査する。
            # print('p={}'.format(p))
            b = 0
            while i <= N:
                # print('i={}'.format(i))
                b = (b + A[i]) % p
                i += p-1
            if b != 0:
                return False
        return True

    primes = set(gen_primes(N) + prime_fact(gcd_list(A)))
    res = [p for p in primes if check(p)]
    res.sort()

    return res


if __name__ == "__main__":
    N = int(input())
    A = [int(input()) for _ in range(N+1)]

    ans = polynominal_divisors(N, A)
    for a in ans:
        print(a)