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: Runtime Error

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:
    if A[N] != 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: Runtime Error

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}
    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)]

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:
    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: Runtime Error

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}
    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)]

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: Runtime Error

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:
    p1 = p0 / 0
    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: Runtime Error

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 a in A[:N]:
    if a != 0: gcd_of_A = gcd(abs(a), 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)
        
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: Runtime Error

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: Runtime Error

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: Runtime Error

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[N] != 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: Runtime Error

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]
    for a in A[1:]:
        g = gcd(g, a)
    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)

Submission status: Runtime Error

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}
    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[N] != 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)
used = set(ans)

divisor_of_An = divisor(A[N])
for div in divisor_of_An:
    if div > N:
        if is_prime(div):
            if gcd_of_A % div == 0 and div not in used: ans.append(div)
ans.sort()
for a in ans: print(a)

Submission status: Runtime Error

Solution code:
from math import sqrt

def divisor(a):
    lim = int(sqrt(a))
    divset = set()
    for i in range(1, lim + 1):
        if a % i == 0:
            divset |= {i, a//i}
    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)]

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]
            index_a += p-1
        if coefficient % p > 0: break
    else: ans.append(p)
used = set(ans)

divisor_of_An = divisor(A[N])
for div in divisor_of_An:
    if div > 1:
        if is_prime(div):
            for a in A:
                if a % div > 0: break
            else:
                if div not in used: 
                    ans.append(div)
ans.sort()
for a in ans: print(a)

Submission status: Runtime Error

Solution code:
# E

# 入力
# input
N = int(input())
a_list = [0]*(N+1)
for i in range(N+1):
    a_list[N-i] = int(input())


# 10^5までの素数を計算
# list primes <= 10^5 
primes = list(range(10**5))
primes[0] = 0
primes[1] = 0
for p in range(2, 10**5):
    if primes[p]:
        for i in range(2*p, 10**5, p):
            primes[i] = 0
primes = [p for p in primes if p>0]
p_list = [p for p in primes if p <= N]


# A_Nを素因数分解、Nより大きい素因数をp_listに追加
# A_N, ..., A_0の最大公約数の素因数でやっても同じ
# list prime factors of A_N, if greater then N, add to p_list
# you can use prime factors of gcd(A_N, ..., A_0) instead 

p_list = []
A = abs(a_list[-1])
for p in primes:
    if A % p == 0:
        if p > N:
            p_list.append(p)
        while A % p == 0:
            A = A // p
if A != 0:
    p_list.append(A)

# 個別に条件確認
# check all p in p_list
# x^p ~ x (mod p)
res_list = []
for p in p_list:
    r = 0
    check_list = [0]*(N+1)
    for i in range(p):
        check_list[i] = a_list[i]
    for i in range(p, N+1):
        check_list[(i-1) % (p-1) + 1] += a_list[i]
    for i in range(p):
        if check_list[i] % p != 0:
            r = 1
    if r == 0:
        res_list.append(p)

for p in res_list:
    print(p)

Submission status: Runtime Error

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)

p0 = prime_division(a[0])
#ps = [2,3,5,7,11,13]
ps = [x[0] for x in p0 if x[0]<15]
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: Runtime Error

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n /= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

N = int(input())
A = [int(input()) for i in range(N+1)][::-1]
A.reverse()
g = abs(A[0])
for a in A:
     g = gcd(g,abs(a))
d = prime_decomposition(g)
ans = [p for p in d]

prime = eratosthenes(N+1)

for p in prime:
    if A[0]%p != 0:
        continue
    for n in range(1,p):
        s = 0
        for k in range(int((N-n)/(p-1))+1):
            s += A[n+k*(p-1)]
            s %= p
        if s != 0:
            break
    if s == 0:
        ans.append(p)

ans = list(set(ans))
ans.sort()

for p in ans:
    print(p)

Submission status: Runtime Error

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n /= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

N = int(input())
A = [int(input()) for i in range(N+1)][::-1]
A.reverse()
g = abs(A[0])
for a in A:
     g = gcd(g,abs(a))
d = prime_decomposition(g)
ans = [p for p in d]

prime = eratosthenes(N+1)

for p in prime:
	if A[0]%p != 0:
    	continue
    for n in range(1,p):
        s = 0
        for k in range(int((N-n)/(p-1))+1):
            s += A[n+k*(p-1)]
            s %= p
        if s != 0:
            break
    if s == 0:
        ans.append(p)

ans = list(set(ans))
ans.sort()

for p in ans:
    print(p)

Submission status: Runtime Error

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n /= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

N = int(input())
A = [int(input()) for i in range(N+1)]
g = A[0]
for a in A:
     g = gcd(g,a)
d = prime_decomposition(g)
ans = [p for p in d]

prime = eratosthenes(N+1)
A.reverse()
for p in prime:
    if A[0]%p != 0:
        continue
    for n in range(1,p+1):
        s = 0
        for k in range(int((N-n)/(p-1))+1):
            s += A[n+k*(p-1)]
            s %= p
        if s != 0:
            break
    if s == 0:
        ans.append(p)

ans = list(set(ans))
ans.sort()

for p in ans:
    print(p)

Submission status: Runtime Error

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n /= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

N = int(input())
A = [int(input()) for i in range(N+1)]
g = A[0]
for a in A:
     g = gcd(g,a)
d = prime_decomposition(g)
ans = [p for p in d]

prime = eratosthenes(N+2)
A.reverse()
for p in prime:
    if A[0]%p != 0:
        continue
    for n in range(1,p):
        s = 0
        for k in range(int((N-n)/(p-1))+1):
            s += A[n+k*(p-1)]
            s %= p
        if s != 0:
            break
    if s == 0:
        ans.append(p)

ans = list(set(ans))
ans.sort()

for p in ans:
    print(p)

Submission status: Runtime Error

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n /= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime

N = int(input())
A = [int(input()) for i in range(N+1)]
g = A[0]
for a in A:
     g = gcd(g,a)
d = prime_decomposition(g)
ans = [p for p in d]

prime = eratosthenes(N+2)
A.reverse()
for p in prime:
    if A[-1]%p != 0:
        continue
    for n in range(1,p):
        s = 0
        for k in range(int((N-n)/(p-1))+1):
            s += A[n+k*(p-1)]
            s %= p
        if s != 0:
            break
    if s == 0:
        ans.append(p)

ans = list(set(ans))
ans.sort()

for p in ans:
    print(p)

Submission status: Runtime Error

Solution code:
def eratosthenes(n):
    l=[1]*n;r=[]
    for i in range(2,n+1):
        if l[i-1]!=0:
            r+=[i];j=2
            while i*j<=n:l[i*j-1]=0;j+=1
    return r
Ps = eratosthenes(40000)
def divisor(n):
    for p in Ps:
        if p*p>n:return -1
        if n%p==0:return p
def prime_division(n):
    d={}
    while n>1:
        p=divisor(n)
        if p==-1:d[n]=d.get(n,0)+1;break
        else:d[p]=d.get(p,0)+1;n//=p
    return d
from functools import reduce
def gcd_(a,b):
  if a==0:return 0
  if a<0:return gcd_(-a,b)
  if a>b:return gcd_(b,a)
  if b%a==0:return a
  return gcd_(b,a-b)
def gcd(*numbers):return reduce(gcd_, numbers)

N=int(input())
A=[int(input())for _ in[0]*-~N]
G=sorted(set(prime_division(gcd(*A)).keys())|set(eratosthenes(N)))

def div(p):
    if A[-1]%p!=0:return A[-1]%p
    l=[a%p for a in A[p:]]
    r=[a%p for a in A[:p]]
    ind=0
    for i in range(N-p+1):
        a=r[ind];ind+=1
        r[-1]=(r[-1]+a)%p
        r+=[l[i]]
    return sum(r[-p:])

for p in G:
    if p>N:break
    if div(p)==0:print(p)

Submission status: Runtime Error

Solution code:
def eratosthenes(n):
    l=[1]*n
    r=[]
    for i in range(2,n+1):
    #i=2
    #while i<=n:
        if l[i-1]!=0:
            r+=[i]
            j=2
            while i*j<=n:
                l[i*j-1]=0
                j+=1
    #    i+=1
    return r
Ps = eratosthenes(40000)
def divisor(n):
    for p in Ps:
        if p*p>n:return -1
        if n%p==0:return p
def prime_division(n):
    d={}
    while n>1:
        p=divisor(n)
        if p==-1:d[n]=d.get(n,0)+1;break
        else:d[p]=d.get(p,0)+1;n//=p
    return d
from functools import reduce
def gcd_(a,b):
  if a==0:return 0
  if a<0:return gcd_(-a,b)
  if a>b:return gcd_(b,a)
  if b%a==0:return a
  return gcd_(b,a-b)
def gcd(*numbers):
    return reduce(gcd_, numbers)

N=int(input())
A=[int(input())for _ in[0]*-~N]
G=sorted(set(prime_division(gcd(*A)).keys())|set(eratosthenes(N)))

def div(p):
    if A[-1]%p!=0:return A[-1]%p
    l=[a%p for a in A]
    r=[a%p for a in A[:p]]
    ind=0
    for i in range(N-p+1):
        a=r[ind];ind+=1
        r[-1]=(r[-1]+a)%p
        r+=[l[p+i]]
    return sum(r[-p:])

for p in G:
    if div(p)==0:print(p)

Submission status: Runtime Error

Solution code:
def eratosthenes(n):
    l=[1]*n
    r=[]
    for i in range(2,n+1):
    #i=2
    #while i<=n:
        if l[i-1]!=0:
            r+=[i]
            j=2
            while i*j<=n:
                l[i*j-1]=0
                j+=1
    #    i+=1
    return r
Ps = eratosthenes(40000)
def divisor(n):
    for p in Ps:
        if p*p>n:return -1
        if n%p==0:return p
def prime_division(n):
    d={}
    while n>1:
        p=divisor(n)
        if p==-1:d[n]=d.get(n,0)+1;break
        else:d[p]=d.get(p,0)+1;n//=p
    return d
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)

N=int(input())
A=[int(input())for _ in[0]*-~N]
G=sorted(set(prime_division(gcd(*A)).keys())|set(eratosthenes(N)))

def div(p):
    if A[-1]%p!=0:return A[-1]%p
    l=[a%p for a in A]
    r=[a%p for a in A[:p]]
    ind=0
    for i in range(N-p+1):
        a=r[ind];ind+=1
        r[-1]=(r[-1]+a)%p
        r+=[l[p+i]]
    return sum(r[-p:])

for p in G:
    if div(p)==0:print(p)

Submission status: Runtime Error

Solution code:
from math import sqrt

def divisor(a):
    lim = int(sqrt(a))
    divset = set()
    for i in range(1, lim + 1):
        if a % i == 0:
            divset |= {i, a//i}
    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)]

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:
    sum = A[0] % p
    for i in range(1, p):
        coefficient = 0
        index_a = i
        while index_a <= N:
            coefficient += A[index_a]
            index_a += p-1
        sum += coefficient % p
        sum %= p
    if sum % p == 0: ans.append(p)

used = set(ans)

divisor_of_An = divisor(A[N])
for div in divisor_of_An:
    if div > 1:
        if is_prime(div):
            for a in A:
                if a % div > 0: break
            else:
                if div not in used: 
                    ans.append(div)
ans.sort()
for a in ans: print(a)

Submission status: Runtime Error

Solution code:
from math import sqrt

def divisor(a):
    lim = int(sqrt(a))
    divset = set()
    for i in range(1, lim + 1):
        if a % i == 0:
            divset |= {i, a//i}
    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)]

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:
    sum = A[0] % p
    for i in range(1, p):
        coefficient = 0
        index_a = i
        while index_a <= N:
            coefficient += A[index_a]
            index_a += p-1
        sum += coefficient % p
        sum %= p
    if sum % p == 0: ans.append(p)

divisor_of_An = divisor(A[N])
for div in divisor_of_An:
    if div > 1:
        if is_prime(div):
            for a in A:
                if a % div > 0: break
            else:
                if div not in ans: ans.append(div)
ans.sort()
for a in ans: print(a)

Submission status: Runtime Error

Solution code:
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    if x%y==0:
        return y
    else:
        return gcd(x%y,y)
N=int(input())
a=[int(input()) for i in range(N+1)][::-1]
#N=10000
#a=[i+1 for i in range(N+1)]
g=a[0]
for i in range(1,N+1):
    g=gcd(g,a[i])
def check(P):
    b=[a[i]%P for i in range(1,N+1)]
    if N<P:
        for i in b:
            if i!=0:
                return False
        return True
    else:
        c=[0 for i in range(P-1)]
        for i in range(N):
            c[i%(P-1)]+=b[i]
            c[i%(P-1)]%=P
        for i in c:
            if i!=0:
                return False
        return True
Plist=set()
X=[1 for i in range(N+1)]
X[0]=0;X[1]=0
i=2
while(i*i<=N):
    for j in range(i,N+1,i):
        if i==j:
            if X[i]==0:
                break
        else:
            X[j]=0
    i+=2
i=2
tmp=g
while(i*i<=g):
    if tmp%i==0:
        Plist.add(i)
        while(1):
            if tmp%i==0:
                tmp=tmp//i
            else:
                break
if tmp>1:
    Plist.add(tmp)
for j in range(N+1):
    if X[j]==1:
        Plist.add(j)
Plist=sorted(list(Plist))
for p in Plist:
    if check(p):
        print(p)