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 random import randint
import math
from math import gcd
#from fractions import gcd
def is_prime(x):#https://qiita.com/neko_the_shadow/items/4ebad619564a48f5a97f
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

n = int(input())
a=[]
for _ in range(n+1):
    a.append(int(input()))
a.reverse()

prm0 = []
prm02 = []
a0 = a[0]

sq = int(a0**(1/2))+3

for i in range(2,sq):
    if a0%i==0:
        prm0.append(i)
        prm02.append(a0//i)
pr_ = prm0+prm02
pr_.append(a0)
pr = []
for p in pr_:
    if is_prime(p):
        pr.append(p)
#print("test",pr)
def f(x,p):
    res = 0
    for i in range(n+1):
        res += pow(x,i,p)*a[i]
    return res
ans_l = []
pr2 = {p for p in pr}
for _ in range(50):
    ans = a0
    rn = randint(1,a0)
    ans = gcd(ans,f(rn,a0))
    for p in pr:
        if ans%p and p in pr2:
            pr2.remove(p)
    #print(ans)

#ans_l = list(set(ans_l))
#print(ans_l)

for p in pr2:
    print(p)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(input()) for i in range(N+1)]
mod = int(1e+9 + 7)
i = N
while A[i] == 0:
  i -= 1
a = A[i]
B = []
if a < 0:
  a = -a
p = 2
while a != 1:
  j = 0
  while a % p == 0:
    a //= p
    j = 1
  if j != 0:
    B.append(p)
  p += 1
  if p > int(A[i]**(1/2)) and a != 1:
    B.append(a)
    break
C = []
for k in B:
  x = 0
  for j in A:
    if j % k != 0:
      x = 1
  if x == 0:
    C.append(k)
    B.remove(k)
if len(B) != 0:
  M = min(N, max(B))
else:
  M = 0
SL = []
for s in range(1, M+1):
  S = 0
  P = s
  for j in range(1, N+1):
    S += (P * A[N-j]) % mod
    S %= mod
    P *= s
    P %= mod
  SL.append(S)
for y in B:
  l = 0
  for z in range(min(N, y)):
    if SL[z] % y != 0:
      l = 1
  if l == 0:
    C.append(y)
C.sort()
for k in range(len(C)):
  print(C[k])

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(input()) for i in range(N+1)]
i = N
while A[i] == 0:
  i -= 1
a = A[i]
B = []
if a < 0:
  a = -a
p = 2
while a != 1:
  i = 0
  while a % p == 0:
    a //= p
    i = 1
  if i != 0:
    B.append(p)
  p += 1
  if p > int(A[N]**(1/2)) and a != 1:
    B.append(a)
    break
S = sum(A)
C = []
for i in B:
  if S % i == 0:
    C.append(i)
C.sort()
for i in range(len(C)):
  print(C[i])

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(input()) for i in range(N+1)]
a = A[N]
B = []
if a < 0:
  a = -a
p = 2
while a != 1:
  i = 0
  while a % p == 0:
    a //= p
    i = 1
  if i != 0:
    B.append(p)
  p += 1
  if p > int(A[N]**(1/2)) and a != 1:
    B.append(a)
    break
S = sum(A)
C = []
for i in B:
  if S % i == 0:
    C.append(i)
C.sort()
for i in range(len(C)):
  print(C[i])

Submission status: Runtime Error

Solution code:
from random import randint
import math
from fractions import gcd

def is_prime(x):#https://qiita.com/neko_the_shadow/items/4ebad619564a48f5a97f
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

n = int(input())
a=[]
for _ in range(n+1):
    a.append(int(input()))
a.reverse()

prm0 = []
prm02 = []
a0 = a[0]

sq = int(a0**(1/2))+3

for i in range(2,sq):
    if a0%i==0:
        prm0.append(i)
        prm02.append(a0//i)
pr_ = prm0+prm02
pr_.append(a0)
pr = []
for p in pr_:
    if is_prime(p):
        pr.append(p)
#print("test",pr)
def f(x,p):
    res = 0
    for i in range(n+1):
        res += pow(x,i,p)*a[i]
    return res
ans_l = []

for _ in range(50):
    ans = a0
    rn = randint(1,a0)
    ans = gcd(ans,f(rn,a0))
    for p in pr:
        if ans%p:
            pr.remove(p)
    #print(ans)

#ans_l = list(set(ans_l))
#print(ans_l)
for p in pr:
    print(p)

Submission status: Runtime Error

Solution code:
from random import randint,choice
import math
from fractions import gcd

def is_prime(x):#https://qiita.com/neko_the_shadow/items/4ebad619564a48f5a97f
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

n = int(input())
a=[]
for _ in range(n+1):
    a.append(int(input()))
a.reverse()

prm0 = []
prm02 = []
a0 = a[0]

sq = int(a0**(1/2))+3

for i in range(2,sq):
    if a0%i==0:
        prm0.append(i)
        prm02.append(a0//i)
pr_ = prm0+prm02
pr_.append(a0)
pr = []
for p in pr_:
    if is_prime(p):
        pr.append(p)
#print("test",pr)
def f(x,p):
    res = 0
    for i in range(n+1):
        res += pow(x,i,p)*a[i]
    return res
ans_l = []

for p in pr:
    #print(p)
    ans = p
    for _ in range(50):
        rn = randint(1,ans+10)
        ans = gcd(ans,f(rn,p))
    if ans==p:
        ans_l.append(ans)
    #print(ans)

ans_l = list(set(ans_l))
#print(ans_l)
for a in ans_l:
    print(a)

Submission status: Runtime Error

Solution code:
from random import randint,choice
import math
from fractions import gcd

def is_prime(x):#https://qiita.com/neko_the_shadow/items/4ebad619564a48f5a97f
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

n = int(input())
a=[]
for _ in range(n+1):
    a.append(int(input()))
a.reverse()

prm0 = []
prm02 = []
a0 = a[0]

sq = int(a0**(1/2))+3

for i in range(2,sq):
    if a0%i==0:
        prm0.append(i)
        prm02.append(a0//i)
pr_ = prm0+prm02
pr_.append(a0)
pr = []
for p in pr_:
    if is_prime(p):
        pr.append(p)
#print("test",pr)
def f(x,p):
    res = 0
    for i in range(n+1):
        res += pow(x,i,p)*a[i]
    return res
ans_l = []

for p in pr:
    #print(p)
    ans = p
    for _ in range(1000):
        rn = randint(1,ans+10)
        ans = gcd(ans,f(rn,p))
    if ans==p:
        ans_l.append(ans)
    #print(ans)

ans_l = list(set(ans_l))
#print(ans_l)
for a in ans_l:
    print(a)

Submission status: Runtime Error

Solution code:
from random import randint,choice
import math
"""
def gcd(a,b):
    while a!=b and b!=0:
        if a<b:
            tmp = a
            a=b
            b=tmp
        a%=b
        tmp = a
        a= b
        b=tmp
    return(max(a,b))
"""
def is_prime(x):#https://qiita.com/neko_the_shadow/items/4ebad619564a48f5a97f
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

n = int(input())
a=[]
for _ in range(n+1):
    a.append(int(input()))
a.reverse()

prm0 = []
prm02 = []
a0 = a[0]

sq = int(a0**(1/2))+3

for i in range(2,sq):
    if a0%i==0:
        prm0.append(i)
        prm02.append(a0//i)
pr_ = prm0+prm02
pr_.append(a0)
pr = []
for p in pr_:
    if is_prime(p):
        pr.append(p)
#print("test",pr)
def f(x,p):
    res = 0
    for i in range(n+1):
        res += pow(x,i,p)*a[i]
    return res
ans_l = []

for p in pr:
    ans = p
    for _ in range(1000):
        rn = randint(1,ans+7)
        ans = math.gcd(ans,f(rn,p))
    ans_l.append(ans)
ans_l = list(set(ans_l))
for a in ans_l:
    print(a)

Submission status: Runtime Error

Solution code:
n=int(input())
A=[]
for i in range(n+1):
  A.append(int(input()))

d=A[0]

pf={}
for i in range(2,int(d**0.5)+1):
  while d%i==0:
    pf[i]=pf.get(i,0)+1
    d//=i
if d>1:
  pf[d]=1
Ans=list(pf.keys())

for i in range(1,n+1):
  for ans in Ans:
    if A[i]%ans!=0:
      Ans.remove(ans)

def f(x):
  ret=A[-1]
  xx=1
  for i in reversed(range(n)):
    xx*=x
    ret+=A[i]*xx
  return ret

def primes(n):
  if n==0:
    return []
  else:
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
      if not is_prime[i]:
        continue
      for j in range(i * 2, n + 1, i):
        is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

for p in primes(n):
  chk=True
  for i in range(p):
    if f(i)%p!=0:
      chk=False
  if chk==True:
    Ans.append(p)
Ans.sort()
for ans in Ans:
  print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
A=[]
for i in range(n+1):
  A.append(int(input()))
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
d=A[0]
for i in range(1,n):
  d=gcd(d,abs(A[i]))

pf={}
for i in range(2,int(d**0.5)+1):
  while d%i==0:
    pf[i]=pf.get(i,0)+1
    d//=i
if d>1:
  pf[d]=1
Ans=list(pf.keys())

def f(x):
  ret=A[-1]
  xx=1
  for i in reversed(range(n)):
    xx*=x
    ret+=A[i]*xx
  return ret

def primes(n):
  if n==0:
    return []
  else:
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
      if not is_prime[i]:
        continue
      for j in range(i * 2, n + 1, i):
        is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

for p in primes(n):
  chk=True
  for i in range(p):
    if f(i)%p!=0:
      chk=False
  if chk==True:
    Ans.append(p)
Ans.sort()
for ans in Ans:
  print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
A=[]
for i in range(n+1):
  A.append(int(input()))
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
d=A[0]
for i in range(1,n):
  d=gcd(d,abs(A[i]))

pf={}
for i in range(2,int(d**0.5)+1):
  while d%i==0:
    pf[i]=pf.get(i,0)+1
    d//=i
if d>1:
  pf[d]=1
Ans=list(pf.keys())

def f(x):
  ret=A[-1]
  xx=1
  for i in reversed(range(n)):
    xx*=x
    ret+=A[i]*xx
  return ret

def primes(n):
  if n==0:
    return []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
      if not is_prime[i]:
        continue
      for j in range(i * 2, n + 1, i):
        is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

for p in primes(n):
  chk=True
  for i in range(p):
    if f(i)%p!=0:
      chk=False
  if chk==True:
    Ans.append(p)
Ans.sort()
for ans in Ans:
  print(ans)

Submission status: Runtime Error

Solution code:
import sys
from math import sqrt
from fractions import gcd
n = int(input())
a = [int(input()) for _ in range(n+1)]
m = a[0]
for i in range(1, n+1):
	m = gcd(m, abs(a[i]))
ps = []

i = 2
while i**2 <= m:
#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)

prime = []
for i in range(2, n+1):
	for p in prime:
		if i%p == 0:
			break
	else:
		prime.append(i)

ps = sorted(list(set(ps + prime)))
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:
			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: Runtime Error

Solution code:
import sys
from math import sqrt
from math import gcd
n = int(input())
a = [int(input()) for _ in range(n+1)]
m = a[0]
for i in range(1, n+1):
	m = gcd(m, abs(a[i]))
ps = []

i = 2
while i**2 <= m:
#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)

prime = []
for i in range(2, n+1):
	for p in prime:
		if i%p == 0:
			break
	else:
		prime.append(i)

ps = sorted(list(set(ps + prime)))
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:
			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: Runtime Error

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

Submission status: Runtime Error

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
	#x += 1
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]
print("WA")

Submission status: Runtime Error

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
	x += 1
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: Runtime Error

Solution code:
from sys import exit
from math import sqrt
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
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: Runtime Error

Solution code:
from sys import exit
from math import sqrt
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
if x > 0:
	m *= x
#print(m)
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: Runtime Error

Solution code:
from sys import exit
from math import sqrt
n = int(input())
a = [int(input()) for _ in range(n+1)]
if a[n] == 0:
	x = 1
else:
	x = 0
for i in range(n, -1, -1):
	if a[i] != 0:
		a = a[:i+1]
		n = i
		break
#print(a, n)
#m = abs(sum(a))
while True:
	m = abs(sum([a[i]*pow(x, n-i) for i in range(n+1)]))
	if m != 0:
		break
	x += 1
if x > 0:
	m *= x
#print(m)
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 sum(a)%p == 0:
		print(p)

Submission status: Runtime Error

Solution code:
from sys import exit
from math import sqrt
n = int(input())
a = [int(input()) for _ in range(n+1)]
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)

Submission status: Runtime Error

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

def eratosthenes(N):
    from collections import deque
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    ret = []
    for i in range(N+1):
        if work[i]:
            ret.append(i)
            for j in range(2* i, N+1, i):
                work[j] = False
    return ret

N = int( input())
A = [ int( input()) for _ in range(N+1)]
Primes = eratosthenes(N)
ANS = []
F = factors( abs(A[0]))
for f in F:
    if f >= N+1:
        Primes.append(f)
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1): # f が恒等的に 0 であるかどうかのチェック
            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 = 0
        if sum(poly) == 0 and A[N]%p == 0: # a_0 が 0 かつ、g が恒等的に 0 であることをチェックしている
            check = 1
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

Submission status: Runtime Error

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

def eratosthenes(N):
    from collections import deque
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    ret = []
    for i in range(N+1):
        if work[i]:
            ret.append(i)
            for j in range(2* i, N+1, i):
                work[j] = False
    return ret

N = int( input())
A = [ int( input()) for _ in range(N+1)]
Primes = eratosththenes(N)
ANS = []
F = factors( abs(A[0]))
for f in F:
    if f >= N+1:
        Primes.append(f)
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1): # f が恒等的に 0 であるかどうかのチェック
            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 = 0
        if sum(poly) == 0 and A[N]%p == 0: # a_0 が 0 かつ、g が恒等的に 0 であることをチェックしている
            check = 1
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
int N;
ll a[10050];
set<ll> cleared;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for(int i = N; i >= 0; i--) cin >> a[i];
    vector<ll> primes;
    ll copy = a[N];
    for(ll i = 2; i * i <= copy; i++) {
        if(copy % i == 0) {
            primes.push_back(i);
            while(copy % i == 0) copy /= i;
        }
    }
    if(copy > 1) primes.push_back(copy);
    for(int i = 0; i < primes.size(); i++) {
        ll now = primes[i];
        bool ok = true;
        for(int j = 0; j <= N; j++) {
            if(a[j] % now != 0) ok = false;
        }
        if(ok) cleared.insert(now);
    }
    for(ll i = 2; i <= 10000; i++) {
        bool ok = true;
        for(ll j = 2; j * j <= i; j++) {
            if(i % j == 0) ok = false;
        }
        if(!ok) continue;
        //cerr << i << endl;
        vector<ll> v(N + 1);
        for(int j = N; j >= 0; j--) {
            v[j] += a[j];
            if(j-i+1 >= 0) {
                v[j-i+1] -= v[j];
            }
        }
        bool clear = true;
        for(int j = 0; j <= i-1; j++) {
            //cerr << j << " " << v[j] << endl;
            if(v[j] % i != 0) clear = false;
        }
        if(clear) cleared.insert(i);
    }
    for(auto itr = cleared.begin(); itr != cleared.end(); itr++) {
        cout << *itr << endl;
    }
    return 0;
}

Submission status: Runtime Error

Solution code:
import sys
from fractions import gcd


def eratosthenes_generator():
    yield 2
    n = 3
    h = {}
    while True:
        m = n
        if n in h:
            b = h[n]
            del h[n]
        else:
            b = n
            yield n
        m += b << 1
        while m in h:
            m += b << 1
        h[m] = b
        n += 2


def prime(n):
    ret = []
    if n % 2 == 0:
        ret.append(2)
        while n % 2 == 0:
            n >>= 1
    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i == 0:
            ret.append(i)
            while n % i == 0:
                n = n // i
        if n == 1:
            break
    if n > 1:
        ret.append(n)
    return ret


def solve(n, aaa):
    g = abs(aaa[-1])
    for a in aaa[:-1]:
        if a != 0:
            g = gcd(g, abs(a))
    ans = set(prime(g))

    for p in prime(aaa[0]):
        if p > n + 2:
            break
        if p in ans or aaa[0] % p != 0:
            continue
        q = p - 1
        tmp = [0] * q
        for i, a in enumerate(aaa):
            tmp[i % q] += a
        if all(t % p == 0 for t in tmp):
            ans.add(p)

    ans = sorted(ans)
    return ans


n = int(input())
aaa = list(map(int, sys.stdin))
aaa.reverse()
print('\n'.join(map(str, solve(n, aaa))))

Submission status: Runtime Error

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

def eratosththenes(N):
    if N == 0:
        return [0]
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    for i in range(N+1):
        if work[i]:
            for j in range(2* i, N+1, i):
                work[j] = False
    return work


N = int( input())
A = [ int( input()) for _ in range(N+1)]
E = eratosththenes(N)
Primes = [ i for i in range(N+1) if E[i] == 1]
ANS = []
F = factors(A[0])
for f in F:
    if f >= N+1:
        Primes.append(f)
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 or A[N]%p != 0:
            check = 0
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

Submission status: Runtime Error

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

def eratosththenes(N):
    if N == 0:
        return [0]
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    for i in range(N+1):
        if work[i]:
            for j in range(2* i, N+1, i):
                work[j] = False
    return work


N = int( input())
A = [ int( input()) for _ in range(N+1)]
E = eratosththenes(N)
Primes = [ i for i in range(N+1) if E[i] == 1]
ANS = []
F = factors(A[0])
for f in F:
    if f >= N+1:
        Primes.append(f)
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 check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

Submission status: Runtime Error

Solution code:
def p_factors(n):
    if n < 2:
        return []
    
    d = 2
    result = []
    while n > 1 and d*d <= n:
        if n % d == 0:
            result.append(d)
        while n % d == 0:
            n //= d
        d += 1
        
    if n > 1:
        # n is a prime
        result.append(n)
    return result

def sieve_of_eratosthenes(ub):
    # O(n loglog n) implementation.
    # returns prime numbers <= ub.
    if ub < 2:
        return []
    prime = [True]*(ub+1)
    prime[0] = False
    prime[1] = False
    p = 2
    while p*p <= ub:
        if prime[p]:
            # don't need to check p+1 ~ p^2-1 (they've already been checked).
            for i in range(p*p, ub+1, p):
                prime[i] = False
        p += 1
    return [i for i in range(ub+1) if prime[i]]

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

def gcd_list(lst):
    if len(lst) == 0:
        return 0
    if len(lst) == 1:
        return lst[0]
    g = abs(lst[0])
    for l in lst[1:]:
        g = gcd(g, abs(l))
    return g

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

cands = set(sieve_of_eratosthenes(N) + p_factors(gcd_list(A)))
answer = []
A = list(reversed(A))

for p in cands:
    if N >= p:
        # f(x) = Q(x) (x^p - x) + \sum_{i = 0}^{p-2} h_i x^i (mod p), 
        # where h_i = \sum_{j < N, j % (p-1) = i} a_j
        if A[0] % p == 0:            
            for i in range(1, p-2+1):
                h = 0
                flag = True
                j = i
                while j <= N:
                    h = (h + A[j]) % p
                    j += p - 1
                if h != 0:
                    flag = False
                    break
            if flag:
                answer.append(p)
    else:
        rem = [a % p for a in A]
        if sum(rem) == 0:
            answer.append(p)

if answer:
    answer = sorted(answer)
print(*answer, sep='\n')

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):
    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 = {}
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: 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)

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:
    p = 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)