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

Solution code:
def gcd(a, b):
	while a > 0 and b > 0:
		a, b = b, a % b
	return a + b

def st(a, b):
	if b == 0:
		return 1
	if b % 2 == 0:
		q = st(a, b // 2)
		return q * q
	return a * st(a, b - 1)

n = int(input())
a = []
for i in range(n + 1):
	x = int(input())
	a.append(x)
ans = 0
for x in range(1, 24):
	tmp = 0
	r = st(x, n)
	for i in range(0, n + 1):
		tmp += a[i] * r
		r //= x
	ans = gcd(ans, abs(tmp))
v = []
j = 2
while j * j <= ans:
	if ans % j == 0:
		ans //= j
		v.append(j)
	else:
		j += 1
if ans != 1:
	v.append(ans)
v.sort()
for i in range(len(v)):
	if i == 0 or v[i] != v[i - 1]:
		print(v[i])

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
	while a > 0 and b > 0:
		a, b = b, a % b
	return a + b

def st(a, b):
	if b == 0:
		return 1
	if b % 2 == 0:
		q = st(a, b // 2)
		return q * q
	return a * st(a, b - 1)

n = int(input())
a = []
for i in range(n + 1):
	x = int(input())
	a.append(x)
ans = 0
for x in range(1, 26):
	tmp = 0
	r = st(x, n)
	for i in range(0, n + 1):
		tmp += a[i] * r
		r //= x
	ans = gcd(ans, abs(tmp))
v = []
j = 2
while j * j <= ans:
	if ans % j == 0:
		ans //= j
		v.append(j)
	else:
		j += 1
if ans != 1:
	v.append(ans)
v.sort()
for i in range(len(v)):
	if i == 0 or v[i] != v[i - 1]:
		print(v[i])

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
	while a > 0 and b > 0:
		a, b = b, a % b
	return a + b

def st(a, b):
	if b == 0:
		return 1
	if b % 2 == 0:
		q = st(a, b // 2)
		return q * q
	return a * st(a, b - 1)

n = int(input())
a = []
for i in range(n + 1):
	x = int(input())
	a.append(x)
ans = 0
for x in range(1, 32):
	tmp = 0
	r = st(x, n)
	for i in range(0, n + 1):
		tmp += a[i] * r
		r //= x
	ans = gcd(ans, abs(tmp))
v = []
j = 2
while j * j <= ans:
	if ans % j == 0:
		ans //= j
		v.append(j)
	else:
		j += 1
if ans != 1:
	v.append(ans)
v.sort()
for i in range(len(v)):
	if i == 0 or v[i] != v[i - 1]:
		print(v[i])

Submission status: Time Limit Exceeded

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*998244353

 
# 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] % p
    for i in range(p, N+1):
        check_list[(i-1) % (p-1) + 1] += a_list[i] % p
    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)

Submission status: Time Limit Exceeded

Solution code:
# E

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

# 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)

# 個別に条件確認
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: Time Limit Exceeded

Solution code:
# E
import numpy as np

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

# a0を割り切る素数を全部求める
p_list = []
## 10^5までの素数を計算
primes = np.arange(10**5)
primes[:2] = 0
for p in range(2, 10**5):
    if primes[p]:
        primes[2*p::p] = 0
primes = primes[primes>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)

# 個別に条件確認
res_list = []
check_list = np.zeros(N+1, dtype="int")
for p in p_list:
    r = 0
    check_list = check_list*0
    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: Accepted

Solution code:
import sys,math

def I(): return int(sys.stdin.readline().rstrip())

N = I()
a = [I() for _ in range(N+1)]
a.reverse()

ans = set([])

g = a[0]
for i in range(N):
    g = math.gcd(g,a[i+1])

for p in range(2,int(g**.5)+1):
    if g % p == 0:
        ans.add(p)
        g //= p
if g != 1:
    ans.add(g)

if N == 0:
    ans = list(ans)
    ans.sort()
    print(*ans, sep='\n')
    exit()


def sieve_of_eratosthenes(n):
    prime_list = []  # n以下の素数のリスト
    A = [1]*(n+1)    # A[i] = iが素数なら1,その他は0
    A[0] = A[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if A[i]:
            prime_list.append(i)
            for j in range(i**2,n+1,i):
                A[j] = 0
    for i in range(math.floor(math.sqrt(n))+1,n+1):
        if A[i] == 1:
            prime_list.append(i)
    return prime_list


prime_list = sieve_of_eratosthenes(N)

for p in prime_list:  # f(x) が x**p-x で割り切れるかを判定
    if a[0] % p != 0:
        continue
    else:
        for i in range(p-1):
            if i == 0:
                r = 0
                for j in range(p-1,N+1,p-1):
                    r += a[j]
                    r %= p
                if r != 0:
                    break
            else:
                r = 0
                for j in range(i,N+1,p-1):
                    r += a[j]
                    r %= p
                if r != 0:
                    break
        else:
            ans.add(p)

ans = list(ans)
ans.sort()
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
def get_sieve_of_eratosthenes_new(n):
    import math
    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]

def Ind(b,n):
    count=0
    while n%b==0:
        count+=1
        n//=b
    return count

prime=get_sieve_of_eratosthenes_new(10**4+1)

from fractions import gcd

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

a=a[::-1]
ans=set([])
for p in prime:
    data=[0 for i in range(p)]
    for i in range(1,N+1):
        data[(i-1)%(p-1)]+=a[i]%p
        data[(i-1)%(p-1)]%=p
    check=(a[0]%p==0)
    for i in range(p):
        check=check&(data[i]%p==0)
    if check:
        ans.add(p)


n=a[0]
for i in range(N+1):
    n=gcd(n,a[i])

prime=get_sieve_of_eratosthenes_new(32000)

for p in prime:
    i=Ind(p,n)
    if i!=0:
        ans.add(p)
    n//=pow(p,i)

if abs(n)!=1:
    ans.add(abs(n))

ans=list(ans)
ans.sort()
for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

sosuu=[2];n=int(input())
for L in range(3,n+100):
    chk=True
    for L2 in sosuu:
        if L%L2 == 0:chk=False
    if chk==True:sosuu.append(L)
S=set(sosuu)



A=[0]*(n+1)
g=0
for i in range(n+1):
  A[i]=int(input())
P=[]
PP=factorization(abs(A[0]))
for i in range(len(PP)):
  P.append(PP[i][0])
if P==[1]:
  P=[]
P=set(P)
P=S|P
P=list(P)
P.sort()
for i in range(len(P)):
  p=P[i]
  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
    else:
      if B[j]%p!=0:
        b=1
        break
  if b==0:
    print(p)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
from fractions import gcd

N = int(input())
A = np.array([input() for _ in range(N+1)], dtype=np.int64)[::-1]

# x^p-x で割り切れる必要がある
# p > Nのときは、a_Nの約数でなければならない
# a_Nの素因数および、N以下の素数をテストすればよい

U = int(10 ** 4.5 + 10)
is_prime = np.zeros(U+1, dtype = np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(U+1):
    if p*p > U:
        break
    if is_prime[p]:
        is_prime[p*p::2*p] = 0
primes = is_prime.nonzero()[0]

div = primes[A[N] % primes == 0]

cand = set(div)
x = abs(A[N])
for p in cand:
    while x % p == 0:
        x //= p
if x != 1:
    cand.add(x)

cand |= set(primes[primes <= N].tolist())
cand = sorted(cand)

def test(p):
    if A[0] % p != 0:
        return False
    # x^{p-1} - 1で割り切れるかどうか
    if p > N+10:
        return (A % p == 0).all()
    B = np.pad(A,[0,(-N-1)%(p-1)],'constant').reshape(-1,p-1).sum(axis = 0)
    return (B % p == 0).all()

answer = '\n'.join(str(p) for p in cand if test(p))
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
a = list(reversed([int(input()) for i in range(n+1) ]))

prime = [2,3]

for i in range(5,100000):
    f = True
    for p in prime:
        if(p*p > i):break
        if i % p == 0 :
            f = False
            break
    if f :prime.append(i)

def gcd(x,y):
    if(x < y): x,y = y,x
    if(y == 0): return x
    return gcd(y,x % y)

def isprime(x):
    f = True
    for p in prime:
        if(p*p > x):break
        if x % p == 0:
            f = False
            break
    return f

g = 0
for i in a:
    g = gcd(abs(i),g)



for p in prime:
    if (p > n+1):break
    m = [0 for i in range(p-1)]
    if a[0] % p != 0:continue
    for i in range(n+1):
        m[i % (p-1)] += (a[i] % p)
    f = True
    for i in m:
        if i % p > 0 :
            f = False
            break    
    if f:print(p)




for p in prime:
    if g == 1:break
    if(g % p == 0):
        g //= p
        if (p > n+1):print(p)

if(g != 1):
    if isprime(g):print(g)

Submission status: Accepted

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

i = 2
while i**2 <= m and i <= n+1:
	if m%i == 0:
		ps.append(i)
		while m%i == 0:
			m //= i
	i += 1
if m != 1 and n != 0:
	ps.append(m)
g = a[0]
for i in range(1, n+1):
	g = gcd(g, abs(a[i]))

ans = []
i = 2
while i**2 <= g:
	if g%i == 0:
		if i >= n+1:
			ans.append(i)
		while g%i == 0:
			g //= i
	i += 1
if g != 1 and g >= n+1:
	ans.append(g)

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:
			ans.append(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:
				ans.append(p)
ans = sorted(list(set(ans)))
if ans:
	print(*ans, sep="\n")

Submission status: Accepted

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

i = 2
while i**2 <= m and i <= n+1:
#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 and n != 0:
	ps.append(m)
#print(ps)
g = a[0]
for i in range(1, n+1):
	g = gcd(g, abs(a[i]))

#print(g)
ans = []

i = 2
while i**2 <= g:
#for i in range(2, int(sqrt(m))+1):
	if g%i == 0:
		if i >= n+1:
			ans.append(i)
		while g%i == 0:
			g //= i
	i += 1
if g != 1 and g >= n+1:
	ans.append(g)

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:
			ans.append(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:
				ans.append(p)
ans = sorted(list(set(ans)))
if ans:
	print(*ans, sep="\n")

Submission status: Accepted

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):
    if N == 0:
        return []
    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: Accepted

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 or i * i > n:
            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
        if all(sum(aaa[i::q]) % p == 0 for i in range(q)):
            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: Accepted

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 or i * i > n:
            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: Accepted

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 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: Accepted

Solution code:
def e_polynominal_divisors(N, A):
    # 参考: http://drken1215.hatenablog.com/entry/2019/04/21/004100
    from fractions import gcd

    def prime_factorization_dict(n):
        """nを素因数分解したときの素数とその指数の辞書"""
        i, table = 2, {}
        while i**2 <= n:
            table[i] = 0
            while n % i == 0:
                table[i] += 1
                n //= i
            if table[i] == 0:
                table.pop(i)
            i += 1
        if n > 1:
            table[n] = 1
        return table

    def prime_table(n):
        """n以下の素数のリスト(エラトステネスの篩)"""
        if n == 0:
            return []
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False  # 0と1は素数でない
        for j in range(2, int(n**0.5) + 1):
            if not is_prime[j]:
                continue
            for k in range(j * 2, n + 1, j):
                is_prime[k] = False  # jの倍数は素数でない
        return [i for i in range(n + 1) if is_prime[i]]

    # f(x) % p == 0 のとき、f(x)の係数はすべてpの倍数。よって、f(x)の各係数の
    # GCDを求め、それを素因数分解して得られる素数が解である。
    # ただし、係数が0の項は考慮しない。
    g = abs(A[N])
    for a in A:
        if a != 0:
            g = gcd(g, abs(a))
    ans = list(prime_factorization_dict(g).keys())

    a = A[::-1]  # Aは係数が最高次から格納されているが、それを最低次からにする
    # p<=N である素数pについて、f(x)がx**p-xで割れるか？
    # それには、f(x)≡h(x) (mod p) を満たすようなp-1次以下の多項式h(x)について、
    # h(x)≡0 (mod p) ⇔ h(x)の係数がすべてpの倍数である
    # を満たすか判定する
    for p in prime_table(N):
        c = [0] * p
        for d in range(p):
            c[d] = a[d] % p
        # x**p≡x (mod p) なので、インデックスはp-1の周期でループする
        for d in range(p, N + 1):
            r = d % (p - 1)
            if r == 0:
                r = p - 1
            c[r] = (c[r] + a[d]) % p

        for factor in c:
            if factor != 0:
                break
        else:
            # h(x) の係数がすべてpの倍数である。f(x)はx**p-xで割りきれる
            ans.append(p)
    ans = sorted(set(ans))
    return '\n'.join(map(str, ans))

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

Submission status: Accepted

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( 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):
            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: Accepted

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


def factorize(n):
    b = 2
    fct = {}
    while b * b <= n:
        while n % b == 0:
            n //= b
            if b in fct.keys():
                fct[b] += 1
            else:
                fct[b] = 1
        b += 1
    if n > 1:
        fct[n] = 1
    return fct


def gcd(a, b):
    """
    自然数a, b の最大公約数を求める
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


g = abs(A[0])
for a in A:
    g = gcd(g, abs(a))
cand = list(factorize(g).keys())
ans_set = [c for c in cand]


def SieveofEratosthenes(N: int) -> list:
    isPrime = [0] + [1 for _ in range(N-1)]
    numList = [i+1 for i in range(N)]
    for i in range(1, N):
        if isPrime[i] == 1:
            for k in range(i+1, N):
                if (k+1) % (i+1) == 0:
                    isPrime[k] = 0
    returnList = []
    for i, v in enumerate(isPrime):
        if v == 1:
            returnList.append(numList[i])
    return returnList


cand = SieveofEratosthenes(N+1)


def ans(cand):
    for p in cand:
        if A[0] % p != 0:
            continue
        for n in range(1, p):
            cur = 0
            for k in range((N-n)//(p-1)+1):
                cur += A[n+k*(p-1)]
                cur %= p
            if cur != 0:
                break
        if cur == 0:
            ans_set.append(p)
    return ans_set


A.reverse()
ans_set = ans(cand)
ans = sorted(list(set(ans_set)))
for p in ans:
    print(p)

Submission status: Accepted

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( 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):
            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: Accepted

Solution code:
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):
    i = 1
    divset = set()
    while i * i <= a:
        if a % i == 0: divset |= {i, a//i}
        i += 1
    divset.remove(1)
    return divset

def is_prime(a):
    if a <= 3: 
        prime = [False, False, True, True]
        return prime[a]
    i = 2
    while i * i <= a:
        if a % i == 0: return False
        i += 1
    else: return True

N = int(input())
A = [None] * (N+1)
for i in reversed(range(N+1)):
    A[i] = int(input())

primes_bool = [True] * (N + 1)
primes = []
for p in range(2, N+1):
    if primes_bool[p]:
        primes.append(p)
        p_mult = p * 2
        while p_mult <= N:
            primes_bool[p_mult] = False
            p_mult += p

ans = []
used = set()
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): 
        ans.append(d)
        used |= {d}

for p in primes:
    if A[0] % p == 0:
        for i in range(1, p):
            coefficient = 0
            index_a = i
            while index_a <= N:
                coefficient += A[index_a]
                coefficient %= p
                index_a += p-1
            if coefficient > 0: break
        else:
            if p not in used: ans.append(p)

ans.sort()
for a in ans: print(a)

Submission status: Accepted

Solution code:
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):
    i = 1
    divset = set()
    while i * i <= a:
        if a % i == 0: divset |= {i, a//i}
        i += 1
    divset.remove(1)
    return divset

def is_prime(a):
    if a <= 3: 
        prime = [False, False, True, True]
        return prime[a]
    i = 2
    while i * i <= a:
        if a % i == 0: return False
        i += 1
    else: return True

N = int(input())
A = [None] * (N+1)
for i in reversed(range(N+1)):
    A[i] = int(input())

primes_bool = [True] * (N + 1)
primes = []
for p in range(2, N+1):
    if primes_bool[p]:
        primes.append(p)
        p_mult = p * 2
        while p_mult <= N:
            primes_bool[p_mult] = False
            p_mult += p

ans = []
used = set()
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): 
        ans.append(d)
        used |= {d}

for p in primes:
    if A[0] % p == 0:
        for i in range(1, p):
            coefficient = 0
            index_a = i
            while index_a <= N:
                coefficient += A[index_a]
                coefficient %= p
                index_a += p-1
            if coefficient > 0: break
        else:
            if p not in used: ans.append(p)

ans.sort()
for a in ans: print(a)

Submission status: Accepted

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:
    flag = True
    # f(x) = Q(x) (x^p - x) + \sum_{i = 0}^{p-1} h_i x^i (mod p), 
    # where 
    # h_0 = a_0 (i = 0)
    # h_i = \sum_{j < N, j % (p-1) = i} a_j (i = 1, ..., p-2)
    # h_{p-1} = \sum_{j < N, j % (p-1) = 0} a_j - a_0 (i = p-1)
    if A[0] % p != 0:
        flag = False
    else:
        for i in range(1, min(N, p-1) + 1):
            h = 0  
            j = i
            while j <= N:
                h = (h + A[j]) % p
                j += p - 1
            if h != 0:
                flag = False
                break
                
    if flag:
        answer.append(p)

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

Submission status: Accepted

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:
    flag = True
    # 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:
        flag = False
    else:
        for i in range(1, min(N, p-1) + 1):
            h = 0  
            j = i
            while j <= N:
                h = (h + A[j]) % p
                j += p - 1
            if h != 0:
                flag = False
                break
                
    if flag:
        answer.append(p)

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