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:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from collections import Counter
from io import BytesIO, IOBase

import _random

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    from builtins import str as __str__

    str = lambda x=b"": x if type(x) is bytes else __str__(x).encode()

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "r" not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines += b.count(b"\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


def gcd(x, y):
    """ greatest common divisor of x and y """
    while y:
        x, y = y, x % y
    return x


gcdm = lambda *args: reduce(gcd, args, 0)


class Random(_random.Random):
    def shuffle(self, x):
        for i in range(len(x) - 1, 0, -1):
            j = int(self.random() * (i + 1))
            x[i], x[j] = x[j], x[i]

    randrange = lambda self, a, b, step=1: a + step * int(self.random() * ((b - a + step + [1, -1][step < 0]) // step))
    randint = lambda self, a, b: a + int(self.random() * (b - a + 1))
    choice = lambda self, seq: seq[int(self.random() * len(seq))]


randint = Random().randint


def memodict(f):
    """ Memoization decorator for a function taking a single argument. """

    class memodict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret

    return memodict().__getitem__


@memodict
def pollard_rho(n):
    if n == 1:
        return Counter()

    d = n - 1
    while not d & 1:
        d >>= 1

    flag = True
    for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
        p, i = pow(a, d, n), d
        while p != 1 and p != n - 1 and i != n - 1:
            i <<= 1
            p = (p * p) % n
        if p != n - 1 and i != d:
            flag = False
            break

    if flag:
        return Counter([n])

    y, c, m = randint(1, n - 1), randint(1, n - 1), randint(1, n - 1)
    g, r, q = 1, 1, 1

    while g == 1:
        x, k = y, 0

        for _ in range(r):
            y = (y * y + c) % n

        while k < r and g == 1:
            ys = y

            for _ in range(min(m, r - k)):
                y = (y * y + c) % n
                q = (q * abs(x - y)) % n

            g = gcd(q, n)
            k += m

        r *= 2

    if g == n:
        while True:
            ys = (ys * ys + c) % n
            g = gcd(abs(x - ys), n)
            if g > 1:
                break

    return pollard_rho(g) + pollard_rho(n // g)


@memodict
def prime_factors(n):
    """ Prime factorization using Pollard's rho algorithm. """
    factors = Counter()

    for p in [2, 3, 5, 13, 19, 73, 193, 407521, 299210837]:
        if n % p == 0:
            cnt = 0
            while n % p == 0:
                n, cnt = n // p, cnt + 1
            factors[p] = cnt

    return factors + pollard_rho(n)


def main():
    n = int(input())
    a = [int(input()) for _ in range(n + 1)]

    g = gcd(sum(a), a[-1])

    for f in prime_factors(g):
        print(f)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
N = int(input())

a = int(input())

for i in range(N):
    b = int(input())
    a = math.gcd(a, b)


n = 2
limit = math.sqrt(a)
while True:
    if a == 1:
        break
    if n > limit:
        print(a)
        break
    if a % n == 0:
        print(n)
        while a % n == 0:
            a //= n
    n += 1

Submission status: Runtime Error

Solution code:
def expmod(a, b, m):
	if b==0: return 1
	cuad=expmod(a*a%m, b/2, m)
	if b%2==1:
		cuad*=a
		cuad%=m
	return cuad

n=int(raw_input())
a=[]
for i in xrange(n+1):
	a.append(int(raw_input()))
pos=[]
last=abs(a[-1])
for p in xrange(2, int(abs(a[-1])**0.5)+2):
	if last<p: break
	if last%p==0:
		while last%p==0: last/=p
		pos.append(p)
if last!=1:
	pos.append(last)
posta=[]
for p in pos:
	vale=True
	for x in xrange(1, 200):
		tot=0
		for i, ai in enumerate(a):
			tot+=expmod(x, n-i, p)*(ai%p)
			tot%=p
		if tot!=0:
			vale=False
			break
	if vale: posta.append(p)
for i in posta:
	print i

Submission status: Runtime Error

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:
    C=[X[-1]]
    

tmax=2
kflag=0
Q=0
while(1):
    Q+=1
    Cnew=[]
    z=random.randint(1,max(C)-1)
    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: Runtime Error

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

results = [0] * (N+1) # 0 .. N までの整数の結果を入れる

for n in range(N+1):
    # x = n として計算する。
    tmp = A[0]
    for i in range(1,N+1):
        tmp *= n
        tmp = (tmp+A[i])
    results[n] = tmp

from fractions import gcd
from functools import reduce

result_gcd = reduce(gcd, results)
# print(result_gcd)
# print(results)

def get_sosu(num):
    lst = []
    for i in range(2, int(num**0.5)+1):
        if num % i == 0 and all( i % lst[i] != 0 for i in range(len(lst)) ):
            lst.append(i)
            lst.append( num // i )
    return lst


lst = get_sosu(result_gcd)

# def primes(n):
#     """ Returns  a list of primes < n """
#     sieve = [True] * n
#     for i in range(3,int(n**0.5)+1,2):
#         if sieve[i]:
#             sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
#     return [2] + [i for i in range(3,n,2) if sieve[i]]

import random
 
def is_Prime(n):
    """
    Miller-Rabin primality test.
 
    A return value of False means n is certainly not prime. A return value of
    True means n is very likely a prime.
    """
    if n!=int(n):
        return False
    n=int(n)
    #Miller-Rabin test for prime
    if n==0 or n==1 or n==4 or n==6 or n==8 or n==9:
        return False
 
    if n==2 or n==3 or n==5 or n==7:
        return True
    s = 0
    d = n-1
    while d%2==0:
        d>>=1
        s+=1
    assert(2**s * d == n-1)
 
    def trial_composite(a):
        if pow(a, d, n) == 1:
            return False
        for i in range(s):
            if pow(a, 2**i * d, n) == n-1:
                return False
        return True  
 
    for i in range(8):#number of trials 
        a = random.randrange(2, n)
        if trial_composite(a):
            return False
 
    return True  
# _pr = primes(10**9)
if is_Prime(result_gcd):
    lst.append(result_gcd)

if len(lst) == 0:
    print("")
    exit()
else:
    for l in lst:
        print(l)

Submission status: Runtime Error

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

check_list = [0]*(N+1)

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

Submission status: Runtime Error

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

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)
    ans = factorize(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: Runtime Error

Solution code:
import math

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

a = a_list[-1]

def primeFactors(n): 
      
    # Print the number of two's that divide n 
    while n % 2 == 0: 
        print(2) 
        n = n // 2
          
    # n must be odd at this point 
    # so a skip of 2 ( i = i + 2) can be used 
    for i in range(3,int(math.sqrt(n))+1,2): 
          
        # while i divides n , print i ad divide n 
        while n % i== 0: 
            print(i)
            n = n / i 
              
    # Condition if n is a prime 
    # number greater than 2 
    if n > 2: 
        print(n) 

primeFactors(a)

Submission status: Runtime Error

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

yakusuu = []
for i in range(1, int(total**(1/2))+1):
    if total % i == 0:
        yakusuu.append(i)
        yakusuu.append(total//i)

import random
def is_prime(q,k=150):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q&1 == 0:
        return False

    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)

        while t != q-1 and y != 1 and y != q-1:
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

primelist = []
for i in yakusuu:
    if is_prime(i):
        primelist.append(i)

primelist.sort()

ans = []
for prime in primelist:
    flag = 1
    for j in range(N+1):
        fx = 0
        for i in range(1000//len(primelist)):
            fx += a[i] * j**(N-i)
        if fx % prime == 0:
            continue
        else:
            flag = 0
    if flag == 1:
        print(prime)

Submission status: Runtime Error

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

yakusuu = []
for i in range(1, int(total**(1/2))+1):
    if total % i == 0:
        yakusuu.append(i)
        yakusuu.append(total//i)

import random
def is_prime(q,k=50):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q&1 == 0:
        return False

    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)

        while t != q-1 and y != 1 and y != q-1:
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

primelist = []
for i in yakusuu:
    if is_prime(i):
        primelist.append(i)

primelist.sort()

ans = []
for prime in primelist:
    flag = 1
    for j in range(N+1):
        fx = 0
        for i in range(N+1):
            fx += a[i] * j**(N-i)
        if fx % prime == 0:
            continue
        else:
            flag = 0
    if flag == 1:
        print(prime)

Submission status: Runtime Error

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)
    ans = factorize(a[-1])
    j = 0
    while j < len(ans):
        b = [a[i]%ans[j] for i in range(n+1)]
        for k in range(n-ans[j]+1):
            b[k+ans[j]-1] -= b[k]
            b[k+ans[j]-1] %= mod
            b[k] = 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: Runtime Error

Solution code:
#!/usr/bin/env python3

import functools
import math

n = int(input())
A = [int(input()) for _ in range(n + 1)]
p = functools.reduce(math.gcd, (sum(i ** (n - j) * a for j, a in enumerate(A)) for i in range(-1000, 1000)))

for i in range(2, int(p ** 0.5) + 1):
    if p % i == 0:
        print(i)
        while p % i == 0:
            p //= i
if p >= 2:
    print(p)

Submission status: Runtime Error

Solution code:
// Created by sz
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 50 + 5;
int n;

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}



int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;
    
    int a,b;
    cin>>a;
    a = abs(a);
    for (int i = 0; i < n; i++){
        cin>>b;
        a = gcd(a, abs(b));
        if(i == n-1&&b%2 ==0)cout<<2<<endl;
    }
    
    if(a == 1){
        cout<<endl;
        return 0;
    }
    
    int m = sqrt(a + 0.5);
    for (int i = 3; i <= m; i++){
        if(a%i==0)cout<<i<<endl;
        while (a%i == 0) {
            a/= i;
        }
        if(a==1) break;
    }
    
    if(a>1)cout<<a<<endl;
    
    
    
    
    
    
    
    return 0;
}

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 == 0: return False
    else: return True

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

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

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

yakusuu = []
for i in range(1, int(total**(1/2))+1):
    if total % i == 0:
        yakusuu.append(i)
        yakusuu.append(total//i)

import random
def is_prime(q,k=50):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q&1 == 0:
        return False

    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)

        while t != q-1 and y != 1 and y != q-1:
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

primelist = []
for i in yakusuu:
    if is_prime(i):
        primelist.append(i)

primelist.sort()

ans = []
for prime in primelist:
    flag = 1
    for j in range(100):
        fx = 0
        for i in range(N+1):
            fx += a[i] * j**(N-i)
        if fx % prime == 0:
            continue
        else:
            flag = 0
    if flag == 1:
        print(prime)