Problem:


Score : 800 points

Problem Statement

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

Constraints

0 \leq N \leq 10^4

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

a_N \neq 0

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_N
:
a_0

Output

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

Sample Input 1

2
7
-7
14

Sample Output 1

2
7

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

Sample Input 2

3
1
4
1
5

Sample Output 2

There may be no integers that satisfy the condition.

Sample Input 3

0
998244353

Sample Output 3

998244353



Sample input:
2
7
-7
14


Sample output:
2
7

Submission status: Wrong Answer

Solution code:
def 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 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(A[-1]))
    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: Wrong Answer

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

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

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

    return res


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

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

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

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

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

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

    return primes


def 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, p):
            # ai + a{i+p-1} + ... を求めて
            # p で割り切れるか検査する。
            b = 0
            while i <= N:
                b = (b + A[i]) % p
                i += p-1
            if b != 0:
                return False
        return True

    primes = set([p for p in gen_primes(N) if check(p)] + prime_fact(A[-1]))

    return sorted(primes)


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:
# 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 != 0:
    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)

Submission status: Wrong Answer

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


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

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

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

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

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

Submission status: Wrong Answer

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


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

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

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

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

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

Submission status: Wrong Answer

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


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

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

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

p0 = prime_division(abs(a[0]))
#ps = [2,3,5,7,11,13]
ps = [x[0] for x in p0 if x[0]<30]
ddprint("ps:")
ddprint(ps)
for p in ps:
    if p in b:
        continue
    ok = True
    for r in range(1,p):
        v = a[0]
        r2i = 1
        for i in range(1,n+1):
            r2i = (r2i * r) % p
            v = (v + a[i] * r2i) % p
        if v != 0:
            ok = False
            break
    if ok:
        b.append(p)

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

Submission status: Wrong Answer

Solution code:
import numpy as np
from functools import reduce
from fractions import gcd as gcd_
def eratosthenes(n):
    is_prime = np.ones((n+1,), dtype=bool)
    is_prime[:2] = False
    for i in range(2,n+1):
        if is_prime[i]:
            is_prime[i*2::i]=False
    return np.arange(n+1)[is_prime]
Ps = eratosthenes(31623)
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
def gcd(*numbers):return reduce(gcd_, numbers)

N=int(input())
A=np.array([int(input())for _ in[0]*-~N])
g_A=gcd(*A)
gcds=set(prime_division(g_A).keys())
eras=set(eratosthenes(N))
G=sorted(gcds|eras)
A=A/g_A
def div(p):
    if p in gcds:return True
    if A[-1]%p!=0:return False
    f=np.poly1d(A)
    if sum(f)==0:return True
    l=np.zeros((p+1,));l[0]=1;l[-2]=-1
    g=np.poly1d(l)
    _,r=f/g
    return all(r % p == 0)

for p in G:
    if div(p):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 = [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(abs(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: Wrong Answer

Solution code:
import numpy as np
from functools import reduce
from fractions import gcd as gcd_
def eratosthenes(n):
    is_prime = np.ones((n+1,), dtype=bool)
    is_prime[:2] = False
    for i in range(2,n+1):
        if is_prime[i]:
            is_prime[i*2::i]=False
    return np.arange(n+1)[is_prime]
Ps = eratosthenes(1000000)
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
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
    if sum([a%p for a in A])==0:return 0
    f=np.poly1d([a%p for a in A])
    l=[0]*(p+1);l[0]=1;l[-2]=-1
    g=np.poly1d(l)
    q,r=f/g
    return sum([k%p for k in r.c])

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

Submission status: Wrong Answer

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(1000000)
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
from fractions import gcd as gcd_
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)))
import numpy as np
def div(p):
    if A[-1]%p!=0:return A[-1]%p
    if sum([a%p for a in A])==0:return 0
    f=np.poly1d([a%p for a in A])
    l=[0]*(N+1);l[0]=1;l[-2]=-1
    g=np.poly1d(l)
    q,r=f/g
    return sum([k%p for k in r.c])

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

Submission status: Wrong Answer

Solution code:
import numpy as np
from functools import reduce
from fractions import gcd as gcd_
def eratosthenes(n):
    is_prime = np.ones((n,), dtype=bool)
    is_prime[:2] = False
    for i in range(2,n):
        if is_prime[i]:
            is_prime[i*2::i]=False
    return np.arange(n)[is_prime]
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
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
    if sum([a%p for a in A])==0:return 0
    f=np.poly1d([a%p for a in A])
    l=[0]*(p+1);l[0]=1;l[-2]=-1
    g=np.poly1d(l)
    q,r=f/g
    return sum([k%p for k in r.c])

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

Submission status: Wrong Answer

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
from fractions import gcd as gcd_
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)))
import numpy as np
def div(p):
    if A[-1]%p!=0:return A[-1]%p
    if sum([a%p for a in A])==0:return 0
    f=np.poly1d([a%p for a in A])
    l=[0]*(p+1);l[0]=1;l[-2]=-1
    g=np.poly1d(l)
    q,r=f/g
    return sum([k%p for k in r.c])

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

Submission status: Wrong Answer

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
from fractions import gcd as gcd_
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)))
import numpy as np
def div(p):
    if A[-1]%p!=0:return A[-1]%p
    if sum([a%p for a in A])==0:return 0
    f=np.poly1d([a%p for a in A])
    l=[0]*(N+1);l[0]=1;l[-2]=-1
    g=np.poly1d(l)
    q,r=f/g
    return sum([k%p for k in r.c])

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

Submission status: Wrong Answer

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):
    if n < 2:
        return []
    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

def ok(p):
    if A[0]%p != 0:
        return False
    B = [A[i]%p for i in range(1,N+1)]
    mod = [0]*(p-1)
    for i in range(N):
        mod[i%(p-1)] += B[i]
        mod[i%(p-1)] %= p
    return sum(mod)==0

N = int(input())
A = [int(input()) for i in range(N+1)][::-1]
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 ok(p):
        ans.append(p)

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

for p in ans:
    print(p)

Submission status: Wrong Answer

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):
    if n < 2:
        return []
    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

def ok(p):
    if A[0]%p != 0:
        return False
    B = [A[i]%p for i in range(1,N+1)]
    mod = [0]*(p-1)
    for i in range(N):
        mod[i%(p-1)] += B[i]
        mod[i%(p-1)] %= p
    return sum(mod)==0

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

prime = eratosthenes(N+1)

for p in prime:
    if ok(p):
        ans.append(p)

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

for p in ans:
    print(p)

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を割り切る素数を全部求める
 
## 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_small = [p for p in primes if p <= N]
p_list_large = []
## 素因数分解
A = 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)
 
# 個別に条件確認
res_list = []
check_list = [0]*(N+1)
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):
        r += check_list[i] % p
    if r == 0:
        res_list.append(p)

check_list = [0]*(N+1)
for p in p_list_large:
    r = 0
    check_list = [0]*(N+1)
    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)

Submission status: Wrong Answer

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):
    if n < 2:
        return []
    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

def ok(p):
    if A[0]%p != 0:
        return False
    B = [A[i]%p for i in range(1,N+1)]
    mod = [0]*(p-1)
    for i in range(N):
        mod[i%(p-1)] += B[i]
        mod[i%(p-1)] %= p
    return sum(mod)==0

N = int(input())
A = [int(input()) for i in range(N+1)][::-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)

for p in prime:
    if ok(p):
        ans.append(p)

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

for p in ans:
    print(p)

Submission status: Wrong Answer

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):
    if n < 2:
        return []
    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):
        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: Wrong Answer

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):
    if n < 2:
        return []
    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):
        s = 0
        for k in range(int((N-n)/(p-1))+1):
            s += A[n+k*(p-1)]
            print(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: 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を割り切る素数を全部求める

## 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_small = [p for p in primes if p <= N]
p_list_large = []
## 素因数分解
A = 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)

# 個別に条件確認
res_list = []
check_list = [0]*(N+1)
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):
        r += check_list[i] % p
    if r == 0:
        res_list.append(p)

check_list = [0]*(N+1)
for p in p_list_large:
    r = 0
    check_list = [0]*(N+1)
    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)

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を割り切る素数を全部求める

## 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_small = [p for p in primes if p <= N]
p_list_large = []
## 素因数分解
A = 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)

# 個別に条件確認
res_list = []
check_list = [0]*(N+1)
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):
        r += check_list[i] % p
    if r == 0:
        res_list.append(p)

check_list = [0]*(N+1)
for p in p_list_large:
    r = 0
    #check_list = [0]*(N+1)
    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)

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を割り切る素数を全部求める

## 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_small = [p for p in primes if p <= N]
p_list_large = []
## 素因数分解
A = 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)

# 個別に条件確認
res_list = []
check_list = [0]*(N+1)
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):
        r += check_list[i] % p
    if r == 0:
        res_list.append(p)

check_list = [0]*(N+1)
for p in p_list_small:
    r = 0
    #check_list = [0]*(N+1)
    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)

Submission status: Wrong Answer

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(100000)
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
from fractions import gcd as gcd_
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
    if sum([a%p for a in A])==0:return 0
    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 div(p)==0:print(p)

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を割り切る素数を全部求める
 
## 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 = 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 > 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(min(p, N+1)):
        r += check_list[i] % p
    if r == 0:
        res_list.append(p)
        
for p in res_list:
    print(p)