Problem:


Score : 800 points

Problem Statement

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

Constraints

0 \leq N \leq 10^4

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

a_N \neq 0

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_N
:
a_0

Output

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

Sample Input 1

2
7
-7
14

Sample Output 1

2
7

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

Sample Input 2

3
1
4
1
5

Sample Output 2

There may be no integers that satisfy the condition.

Sample Input 3

0
998244353

Sample Output 3

998244353



Sample input:
2
7
-7
14


Sample output:
2
7

Submission status: Wrong Answer

Solution code:
import math
import time
import random

t1 = time.time() 

#euclid
A=[2*k+1 for k in range(1,15813)]
p=[2]

while(1):
    y=A.pop(0)
    if y > math.sqrt(15813):
        break
    p.append(y)
    A=[x for x in A if x%y!=0]
p=p+A
N=int(input())
X=[]
for i in range(N+1):
    X.append(int(input()))
#cands
C=[x for x in p if X[-1]%x==0]
if len(C)==0 and sum([ X[-1]==x for x in [-1, 0, 1] ])==0 :
    C=[abs(X[-1])]
    

tmax=1
kflag=0
Q=0
while(len(C)!=0):
    Q+=1
    Cnew=[]
    z=random.randint(1,max(C))
    for c in C:
        if kflag:
            break
        S=0
        t2=time.time()
        zz=z%c
        for i in range(N+1):
            S +=  (X[i] * zz ** (N-i))%c
            if ( t2-t1 ) > tmax*0.9:
                kflag=1
        if S%c==0:
            Cnew.append(c)
    if kflag:
        break
    else:
        C=Cnew[:]
for c in sorted(C):
    print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input()) for _ in range(N+1)][::-1]
a0 = A[0]

def prf(m):
    pf = set()
    for i in range(2, int(m**0.5)+1):
        while m % i == 0:
            pf.add(i)
            m //= i
    if m > 1:
        pf.add(m)
    return pf
candi = list(prf(abs(a0)))
for a in A:
    C = []
    for c in candi:
        if not a%c:
            C.append(c)
    candi = C
if not sum(a%2 for a in A) % 2 and 2 not in candi:
    candi.append(2)
candi.sort()
for c in candi:
    print(c)

Submission status: Wrong Answer

Solution code:
from itertools import cycle
from fractions import gcd
from random import randrange

# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n


N = int(input())
A = list(int(input()) for _ in range(N+1))
A.reverse()


a = abs(sum(A))
b = abs(sum(a*b for a,b in zip(A, cycle((1,-1)))))
c = abs(A[0])
g = gcd(gcd(a,b),c)
P = set(prime_factors(g))

CHECK = 10
res = []

for p in P:

	C = [a%p for a in A]

	for _ in range(CHECK):
		x = randrange(1, p)
		def it():
			xp = 1
			for c in C:
				yield c*xp
				xp *= x
				xp %= p
		r = sum(it())%p
		if r != 0:
			break
	else:
		res.append(p)

print(*res, sep='\n')

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 998244353

#C
def C():
    n = I()
    s = S()
    ans = float("inf")
    b = [0 for i in range(n)]
    for i in range(n):
        if s[i] == "#":
            b[i] = 1
    w = [0 for i in range(n)]
    for i in range(n):
        if s[i] == ".":
            w[i] = 1
    b.insert(0,0)
    w.insert(0,0)
    for i in range(n):
        b[i+1] += b[i]
        w[i+1] += w[i]
    for i in range(n+1):
        m = b[i]+w[n]-w[i]
        ans = min(ans,m)
    print(ans)
    return

#D
def D():
    n = I()
    return

#E
def E():
    def factorize(n):
        if n == 1:
            return []
        if n < 4:
            return [n]
        i = 2
        res = []
        m = n
        while i**2 <= n:
            if m%i == 0:
                while m%i == 0:
                    m //= i
                res.append(i)
            i += 1
        if m != 1:
            res.append(m)
        return res
    def f(x,m):
        res = a[-1]%m
        for i in range(n):
            res += a[i]*pow(x,n-i,m)%m
            if res >= m:
                res %= m
        return res
    n = I()
    a = IR(n+1)
    i = n
    while i >= 0:
        if a[i] == 0:
            a.pop(i)
            n -= 1
        i -= 1
    if n == -1:
        print()
        quit()
    ans = factorize(abs(a[-1]))
    j = 0
    while j < len(ans):
        for i in range(101):
            if f(i,ans[j]) != 0:
                ans.pop(j)
                j -= 1
                break
        j += 1
    if len(ans) == 0:
        print()
        quit()
    for i in ans:
        print(i)
    return

#F
def F():
    return


#Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 998244353

#C
def C():
    n = I()
    s = S()
    ans = float("inf")
    b = [0 for i in range(n)]
    for i in range(n):
        if s[i] == "#":
            b[i] = 1
    w = [0 for i in range(n)]
    for i in range(n):
        if s[i] == ".":
            w[i] = 1
    b.insert(0,0)
    w.insert(0,0)
    for i in range(n):
        b[i+1] += b[i]
        w[i+1] += w[i]
    for i in range(n+1):
        m = b[i]+w[n]-w[i]
        ans = min(ans,m)
    print(ans)
    return

#D
def D():
    n = I()
    return

#E
def E():
    def factorize(n):
        if n == 1:
            return []
        if n < 4:
            return [n]
        i = 2
        res = []
        m = n
        while i**2 <= n:
            if m%i == 0:
                while m%i == 0:
                    m //= i
                res.append(i)
            i += 1
        if m != 1:
            res.append(m)
        return res
    def f(x,m):
        res = a[-1]%m
        for i in range(n):
            res += a[i]*pow(x,n-i,m)%m
            if res >= m:
                res %= m
        return res
    n = I()
    a = IR(n+1)
    i = n
    while i >= 0:
        if a[i] == 0:
            a.pop(i)
            n -= 1
        i -= 1
    if n == -1:
        quit()
    ans = factorize(abs(a[-1]))
    j = 0
    while j < len(ans):
        for i in range(101):
            if f(i,ans[j]) != 0:
                ans.pop(j)
                j -= 1
                break
        j += 1
    for i in ans:
        print(i)
    return

#F
def F():
    return


#Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

Solution code:
from itertools import cycle
from fractions import gcd
from random import randrange

# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n


N = int(input())
A = list(int(input()) for _ in range(N+1))
A.reverse()


a = abs(sum(A))
b = abs(sum(a*b for a,b in zip(A, cycle((1,-1)))))
c = abs(A[0])
g = gcd(gcd(a,b),c)
P = set(prime_factors(g))

CHECK = 3
res = []

for p in P:

	C = [a%p for a in A]

	for _ in range(CHECK):
		x = randrange(1, p)
		def it():
			xp = 1
			for c in C:
				yield c*xp
				xp *= x
				xp %= p
		r = sum(it())%p
		if r != 0:
			break
	else:
		res.append(p)

print(*res, sep='\n')

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 polynominal_divisors(N: int, A: list)->list:
    primes = prime_fact(abs(A[-1]))
    f1 = sum(A)

    res = []
    for p in primes:
        if f1 % p == 0:
            res.append(p)
    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: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 998244353

#C
def C():
    n = I()
    s = S()
    ans = float("inf")
    b = [0 for i in range(n)]
    for i in range(n):
        if s[i] == "#":
            b[i] = 1
    w = [0 for i in range(n)]
    for i in range(n):
        if s[i] == ".":
            w[i] = 1
    b.insert(0,0)
    w.insert(0,0)
    for i in range(n):
        b[i+1] += b[i]
        w[i+1] += w[i]
    for i in range(n+1):
        m = b[i]+w[n]-w[i]
        ans = min(ans,m)
    print(ans)
    return

#D
def D():
    n = I()
    return

#E
def E():
    def factorize(n):
        if n == 1:
            return []
        if n < 4:
            return [n]
        i = 2
        res = []
        m = n
        while i**2 <= n:
            if m%i == 0:
                while m%i == 0:
                    m //= i
                res.append(i)
            i += 1
        if m != 1:
            res.append(m)
        return res
    def f(x,m):
        res = a[-1]%m
        for i in range(n):
            res += a[i]*pow(x,n-i,m)%m
            if res >= m:
                res %= m
        return res
    n = I()
    a = IR(n+1)
    i = n
    while i >= 0:
        if a[i] == 0:
            a.pop(i)
            n -= 1
        i -= 1
    if n == -1:
        print()
        quit()
    ans = factorize(abs(a[-1]))
    j = 0
    while j < len(ans):
        for i in range(11):
            if f(i,ans[j]) != 0:
                ans.pop(j)
                j -= 1
                break
        j += 1
    for i in ans:
        print(i)
    return

#F
def F():
    return


#Solve
if __name__ == "__main__":
    E()

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}
    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 = []
sum = 0
for n in range(N+1):
    a = abs(int(input()))
    if a > 0: 
        A.append(a)
        sum += a % 2
        sum %= 2
div_by_two = False
if sum % 2 == 0: div_by_two = True

gcd_of_A = A[0]
for a in A[1:]:
    gcd_of_A = gcd(gcd_of_A, a)

if gcd_of_A > 1:
    commondiv = divisor(gcd_of_A)
    while True:
        A[0] //= gcd_of_A
        newgcd = A[0]
        for a in A[1:]:
            a //= gcd_of_A
            newgcd = gcd(newgcd, a)
        if newgcd == 1: break
        else:
            newdivisor = divisor(newgcd)
            commondiv |= newdivisor
            gcd_of_A = newgcd
    
    primes = []
    for div in commondiv:
        if div > 1 and is_prime(div): primes.append(div)
    primes.sort()
    if primes[0] != 2 and div_by_two: print(2)
    for p in primes: print(p)
elif div_by_two: print(2)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys, collections, bisect, math, itertools
from fractions import gcd 
#input = sys.stdin.readline #文字列入力のときは注意

m = int(input())
#s = input()
#a = [int(i) for i in input().split()]
a = [int(input()) for j in range(m+1)] # 縦「n」行

beki = 0
while a[-1] == 0:
    a.pop()
    beki+=1
if m != len(a)-1:
    m = len(a)
    a.append(0)


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

primes=[]
def get_sieve_of_eratosthenes2():
    prime = []
    data = [i + 1 for i in range(1, 35000)]
    c=abs(a[m])
    while True:
        p = data[0]
        if 35000 <= p*p:
            return prime + data
        if c%p==0: primes.append(p)
        prime.append(p)
        data = [e for e in data if e % p != 0]

get_sieve_of_eratosthenes2()
#print(primes)
if len(primes) == 0 and abs(a[m]) != 1:
    primes.append(abs(a[m]))
n=m
if a[m]==0:
    primes = allprimes

#print(a)
#print(primes)
for p in primes:
    if p > 10**4+5:
        if sum([i%p for i in a]) == 0:
            print(p)
        continue
    coeff = list(reversed(a))
    while len(coeff) > p:
#        print(coeff,p)
        t=coeff.pop()
        coeff[-p+1]+=t
            
#    print(coeff)
    if sum([i%p for i in coeff]) == 0:
        print(p)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 998244353

#C
def C():
    n = I()
    s = S()
    ans = float("inf")
    b = [0 for i in range(n)]
    for i in range(n):
        if s[i] == "#":
            b[i] = 1
    w = [0 for i in range(n)]
    for i in range(n):
        if s[i] == ".":
            w[i] = 1
    b.insert(0,0)
    w.insert(0,0)
    for i in range(n):
        b[i+1] += b[i]
        w[i+1] += w[i]
    for i in range(n+1):
        m = b[i]+w[n]-w[i]
        ans = min(ans,m)
    print(ans)
    return

#D
def D():
    n = I()
    return

#E
def E():
    def factorize(n):
        if n == 1:
            return []
        if n < 4:
            return [n]
        i = 2
        res = []
        m = n
        while i**2 <= n:
            if m%i == 0:
                while m%i == 0:
                    m //= i
                res.append(i)
            i += 1
        if m != 1:
            res.append(m)
        return res
    n = I()
    a = IR(n+1)
    i = n
    while i >= 0:
        if a[i] == 0:
            a.pop(i)
            n -= 1
        i -= 1
    if n == -1:
        print()
        quit()
    ans = factorize(abs(a[-1]))
    j = 0
    while j < len(ans):
        b = [a[i]%ans[j] for i in range(n+1)]
        for i in range(n-ans[j]+1):
            b[i+ans[j]-1] -= b[i]
            b[i+ans[j]-1] %= ans[j]
            b[i] = 0
        if sum(b) != 0:
            ans.pop(j)
            j -= 1
        j += 1
    for i in ans:
        print(i)
    return

#F
def F():
    return


#Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

Solution code:
import fractions

n = int(input())
nums = [int(input()) for _ in range(n + 1)]

for i in range(100):
	if sum([nums[x] * (i ** (n - x)) for x in range(n + 1)]) % 2 == 1:
		break
else:
	print(2)

tmp = abs(nums[0])
for num in nums[1:]:
	tmp = fractions.gcd(tmp, abs(num))

if tmp != 1:
	print(tmp)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

def factorize(n):
    i = 2
    A = defaultdict(int)
    
    while n % i == 0:
        n //= i
        A[i] += 1
    i += 1

    while n != 1 and i * i <= n:
        while n % i == 0:
            n //= i
            A[i] += 1
        i += 2
    if n != 1:
        A[n] += 1

    return A

P = factorize(A[-1])

# f(-p) == 0を満たせば良い 嘘
def f(p):
    mod = 10 ** 9 + 7
    x = 1
    res = 0
    for a in A[::-1]:
        res += x * a
        res %= mod
        x = x * p % mod

    return res

S = sum(A)

for p, v in P.items():
    if S % p == 0:
        print(p)

print()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

def factorize(n):
    i = 2
    A = defaultdict(int)
    
    while n % i == 0:
        n //= i
        A[i] += 1
    i += 1

    while n != 1 and i * i <= n:
        while n % i == 0:
            n //= i
            A[i] += 1
        i += 2
    if n != 1:
        A[n] += 1

    return A

P = factorize(A[-1])

# f(-p) == 0を満たせば良い 嘘
def f(p):
    mod = 10 ** 9 + 7
    x = 1
    res = 0
    for a in A[::-1]:
        res += x * a
        res %= mod
        x = x * p % mod

    return res

if sum(A[:-1]) == 0:
    for k, v in P.items():
        print(k)
    exit()

for p, v in P.items():
    for a in A:
        if a % p != 0:
            break
    else:
        print(p)

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 = []
for i in range(n+1):
    a.append(inn())
g = a[n]
for i in range(n):
    g = gcd(g, a[i])
p = prime_division(abs(g))
for x in p:
    if x[0] != 1:
        print(x[0])

Submission status: Wrong Answer

Solution code:
# E

N = int(input())
a_list = [0]*(N+1)
for i in range(N+1):
    a_list[N-i] = int(input())
"""
import random
N = 10**4
a_list = [0]*(N+1)
for i in range(N+1):
    a_list[N-i] = random.choice(range(10**9))
a_list[0] = 2*3*5*7*11*13*17*19*23
"""

# a0を割り切る素数を全部求める
p_list = []
## 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]

## 素因数分解
A = a_list[0]
for p in primes:
    if A % p == 0:
        p_list.append(p)
    while A % p == 0:
        A = A // p
if A > 1:
    p_list.append(A)
print(p_list)
# 個別に条件確認
res_list = []

for p in p_list:
    r = 0
    check_list = [0]*(N+1)
    for i in range(min(p, N+1)):
        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(N+1):
        r += check_list[i] % p
    if r == 0:
        res_list.append(p)
        
for p in res_list:
    print(p)

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}
    return divset

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

N = int(input())
A = []
for n in range(N+1):
    a = abs(int(input()))
    if a > 0: A.append(a)

gcd_of_A = A[0]
for a in A[1:]:
    gcd_of_A = gcd(gcd_of_A, a)

if gcd_of_A > 1:
    commondiv = divisor(gcd_of_A)
    while True:
        A[0] //= gcd_of_A
        newgcd = A[0]
        for a in A[1:]:
            a //= gcd_of_A
            newgcd = gcd(newgcd, a)
        if newgcd == 1: break
        else:
            newdivisor = divisor(newgcd)
            commondiv |= newdivisor
            gcd_of_A = newgcd
    
    primes = []
    for div in commondiv:
        if div > 1 and is_prime(div): primes.append(div)
    primes.sort()
    for p in primes: print(p)

Submission status: Wrong Answer

Solution code:
from random import randrange
N = int(input())
A = [int(input()) for _ in range(N+1)][::-1]
a0 = A[0]

def prf(m):
    pf = set()
    for i in range(2, int(m**0.5)+1):
        while m % i == 0:
            pf.add(i)
            m //= i
    if m > 1:
        pf.add(m)
    return pf
def f(x, mod):
    return sum(a*pow(x, d, mod)for d, a in enumerate(A))%mod
candi = list(prf(abs(a0)))
candi.sort()
Ans = []
for c in candi:
    for i in range(50):
        t = randrange(1, c)
        F = f(t, c)
        if F % c:
            break
    else:
        Ans.append(c)
for a in Ans:
    print(a)

Submission status: Wrong Answer

Solution code:
from random import randrange
N = int(input())
A = [int(input()) for _ in range(N+1)][::-1]
a0 = A[0]

def prf(m):
    pf = set()
    for i in range(2, int(m**0.5)+1):
        while m % i == 0:
            pf.add(i)
            m //= i
    if m > 1:
        pf.add(m)
    return pf
def f(x, mod):
    return sum(a*pow(x, d, mod)for d, a in enumerate(A))%mod
candi = list(prf(abs(a0)))
Ans = []
for c in candi:
    for i in range(50):
        t = randrange(1, c)
        F = f(t, c)
        if F % c:
            break
    else:
        Ans.append(c)
for a in Ans:
    print(a)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as ddic, deque
from itertools import combinations, permutations, product
import sys
sys.setrecursionlimit(10**6)
stdout = sys.stdout
rr = lambda: raw_input().strip()
rri = lambda: int(raw_input())
rrm = lambda: list(map(int, raw_input().strip().split()))

from fractions import gcd

def factorize(N):
    ans = []
    e = 0
    while N%2 == 0:
        e += 1
        N //= 2
    if e:
        ans.append((2, e))
    d = 3
    while d*d <= N:
        e = 0
        while N%d == 0:
            e += 1
            N //= d
        if e:
            ans.append((d, e))
        d += 2

    if N > 1:
        ans.append((N, 1))
    return ans

MOD1 = 10**9 + 7
MOD2 = 10**9 + 9
def evalu(A, p):
    bucket = [0] * (p - 1)
    for i, x in enumerate(A):
        j = i % (p-1)
        bucket[j] += x
        bucket[j] %= p
        
    if p < 1000:
        for residue in xrange(p):
            bns = 0
            pwr = 1
            for i, coeff in enumerate(bucket):
                bns += pwr * coeff % p
                bns %= p
                pwr *= residue
                pwr %= p
            if bns: return False
        return True
    if not any(bucket): return True
    return False

        
def solve(N, A):
    g = A[0]
    for x in A:
        g = gcd(g, x)
    gfacts = factorize(g)
    ans = {p for p,_ in gfacts}
    a0 = A[0] // g
    afacts = factorize(a0)
    
    for p,_ in afacts:
        if evalu(A, p):
            ans.add(p)
    return ans
    
    

###
N = rri()
A = []
for _ in xrange(N+1):
    A.append(rri())
A = A[::-1]
ans= solve(N, A)
ans = sorted(ans)
for p in ans:
    print p

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

x=abs(A[-1])
y=abs(sum(A))
z=0
for i in range(N):
    z+=A[i]*((-1)**i)

z=abs(z)

#print(x,y,z)

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

x=gcd(gcd(x,y),z)


import math 
L=int(math.sqrt(x))

FACT=dict()

for i in range(2,L+2):
    while x%i==0:
        FACT[i]=FACT.get(i,0)+1
        x=x//i

if x!=1:
    FACT[x]=FACT.get(x,0)+1

F=sorted(FACT.keys())
if len(F)==0:
    sys.exit()
elif F[0]==1:
    print(*F[1:])
else:
    print(*F)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

def factorize(n):
    i = 2
    A = defaultdict(int)
    
    while n % i == 0:
        n //= i
        A[i] += 1
    i += 1

    while n != 1 and i * i <= n:
        while n % i == 0:
            n //= i
            A[i] += 1
        i += 2
    if n != 1:
        A[n] += 1

    return A

P = factorize(A[-1])

if sum(A[:-1]) == 0:
    for k, v in P.items():
        print(k)
else:
    print()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def f(n):
  a=[];f=2
  while f*f<=n:
    if n%f==0:a.append(f);n//=f
    else:f+=1
  if n!=1:a.append(n)
  return set(a)
s=[2];n=int(input())
for L in range(3,n+1):
  c=True
  for M in s:
    if L%M==0:c=False
  if c==True:s.append(L)
A=[int(input())for i in range(n+1)]
P=sorted(list(set(s)|f(abs(A[0]))))
for p in P:
  B=A[0:n+2];b=0
  for j in range(n+1):
    if p+j<n+1:B[j+p-1]=(B[j+p-1]+B[j])%p
    elif B[j]%p!=0:b=1;break
  if b==0:print(p)

Submission status: Time Limit Exceeded

Solution code:
import sys
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 = []

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)
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: Time Limit Exceeded

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 = []
    for i in eratosthenes_generator():
        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 eratosthenes_generator():
        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: Time Limit Exceeded

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]
# primes <= N
p_list_small = [p for p in primes if p <= N]


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

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

# 個別に条件確認
# check all p in p_list_small
# x^p ~ x (mod p)
res_list = []
for p in p_list_small:
    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)
        
# 個別に条件確認
# check all p in p_list_large
# a_i % p == 0
for p in p_list_large:
    r = 0
    for i in range(N+1):
        if a_list[i] % p != 0:
            r = 1
    if r == 0:
        res_list.append(p)
        
for p in res_list:
    print(p)