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 primeFactor(num):
    import math
    ret = []
    for i in range(2, int(math.sqrt(num))+1):
        if num%i==0:
            num//=i
            ret.append(i)
    if num != 1:
        ret.append(num)
        
    return ret
  
*D, = open(0)
data = []
for it in D[1:]:
    data.append(int(it))
data = data[::-1]

# Get prime number
MAX = 10000
prime = [True for it in range(MAX+1)]
prime[0]=False
prime[1]=False
cnt = 0
while cnt<101:
    while prime[cnt]==False:
        cnt +=1
    for i in range(2,MAX):
        if i*cnt > MAX:
            break
        prime[i*cnt]=False
        
    cnt+=1

ret = []
for i,it in enumerate(prime):
    if it:
        ret.append(i)
        
        
        
ans = []
for p in ret:
    if abs(data[0])%p!=0:
        continue
    aaa = [0 for _ in range(p-1)]
    for i in range(1,len(data)):
        aaa[i%(p-1)]+=((data[i]))
        
    SUCCESS = True
    for it in aaa:
        if it%p!=0:
            SUCCESS = False
            break
    if SUCCESS:
        ans.append(p)
    
#
prime = primeFactor(abs(data[0]))
for p in prime:
    if p > 10000:
        SUCCESS = True
        for it in data:
            if it%p!=0:
                SUCCESS = False
                break
        if SUCCESS:
            ans.append(p)
            
            
for it in ans:
    print(it)

Submission status: Wrong Answer

Solution code:
def primeFactor(num):
    import math
    ret = []
    for i in range(2, int(math.sqrt(num))+1):
        if num%i==0:
            num//=i
            ret.append(i)
    if num != 1:
        ret.append(num)
        
    return ret
  
*D, = open(0)
data = []
for it in D[1:]:
    data.append(int(it))
data = data[::-1]

# Get prime number
MAX = 10000
prime = [True for it in range(MAX+1)]
prime[0]=False
prime[1]=False
cnt = 0
while cnt<101:
    while prime[cnt]==False:
        cnt +=1
    for i in range(2,MAX):
        if i*cnt > MAX:
            break
        prime[i*cnt]=False
        
    cnt+=1

ret = []
for i,it in enumerate(prime):
    if it:
        ret.append(i)
        
        
        
ans = []
for p in ret:
    if abs(data[0])%p!=0:
        continue
    aaa = [0 for _ in range(p-1)]
    for i in range(1,len(data)):
        aaa[i%(p-1)]+=(abs(data[i]))
        
    SUCCESS = True
    for it in aaa:
        if it%p!=0:
            SUCCESS = False
            break
    if SUCCESS:
        ans.append(p)
    
#
prime = primeFactor(abs(data[0]))
for p in prime:
    if p > 10000:
        SUCCESS = True
        for it in data:
            if it%p!=0:
                SUCCESS = False
                break
        if SUCCESS:
            ans.append(p)
            
            
for it in ans:
    print(it)

Submission status: Wrong Answer

Solution code:
s=input()[::-1]
a=[]
index=0
while index < len(s)-1:
    if s[index]=="A" and s[index+1]=="W":
        index+=1
        while index!=len(s) and s[index]=="W":
            a.append("C")
            index+=1
        a.append("A")
    else:
        a.append(s[index])
        index+=1
print("".join(a[::-1]))

Submission status: Wrong Answer

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) + 2, 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:
            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: Wrong Answer

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:
            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: Wrong Answer

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 range(2, int(n ** 0.5) + 1):
        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:
            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: Wrong Answer

Solution code:
import functools

n = int(input())
a = []
p = []
is_prime = [True] * (n + 1)

for i in range(0, n + 1):
    a.append(int(input()))

a.reverse()

def gcd(x, y):
    x = abs(x)
    y = abs(y)
    while y != 0:
        x, y = y, x % y
    return x

def td(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            n = n // i
            p.append(i)
        else:
            i += 1
    if n > 1:
        p.append(n)

td(functools.reduce(gcd, a))

def se():
    i = 2
    while i * i <= n:
        if is_prime[i]:
            for j in range(i, n // i + 1):
                is_prime[i * j] = False
        i += 1
se()

def f(x, p):
    s = a[0]
    for i in range(1, n + 1):
        s += (a[i] % p) * pow(x, i, p)
        s %= p
    return s

for i in range(2, n + 1):
    if is_prime[i]:
        fl = True
        for j in range(0, i):
            if f(j, i) != 0:
                fl = False
                break
        if fl:
            p.append(i)

for i in set(p):
    print(i)

Submission status: Wrong Answer

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

    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を求め、それを素因数分解して得られる素数が解である。
    g = reduce(gcd, 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: Wrong Answer

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

    def prime_factorization_dict(n):
        """nを素因数分解したときの素数とその指数の辞書"""
        if n == 1:
            return {}  # 1は素数の0乗の積とみなす
        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を求め、それを素因数分解して得られる素数が解である。
    gcd = reduce(gcd, A)
    ans = list(prime_factorization_dict(gcd).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) % p

        for d in range(p):
            if c[d] != 0:
                break
        else:
            # h(x) の係数がすべてpの倍数である。f(x)はx**p-xで割りきれる
            ans.append(p)
    ans.sort()
    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: Wrong Answer

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

    def prime_factorization_dict(n):
        """nを素因数分解したときの素数とその指数の辞書"""
        if n == 1:
            return {}  # 1は素数の0乗の積とみなす
        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を求め、それを素因数分解して得られる素数が解である。
    gcd = reduce(gcd, A)
    ans = list(prime_factorization_dict(gcd).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) % p

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

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

Submission status: Wrong Answer

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 = 0
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

Submission status: Wrong Answer

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 = list(set(ans_set))
for p in ans:
    print(p)

Submission status: Wrong Answer

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)
A.reverse()


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


ans_set = ans(cand)
ans = list(set(ans_set))
for p in ans:
    print(p)

Submission status: Wrong Answer

Solution code:
# TLEしそう
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 = 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)


def ans(cand):
    for p in cand:
        if A[-1] % 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


ans_set = ans(cand)
ans = list(set(ans_set))
for p in ans:
    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}
    divset.remove(1)
    return divset

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

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

primes_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()
for p in primes:
    for i in range(p-1):
        coefficient = 0
        index_a = i
        while index_a <= N:
            coefficient += A[index_a]
            coefficient %= p
            index_a += p-1
        if coefficient % p > 0: break
    else: 
        ans.append(p)
        used |= {p}
        
gcd_of_A = abs(A[N])
for a in A[:N]:
    if a != 0: gcd_of_A = gcd(abs(a), gcd_of_A)

commondiv = divisor(gcd_of_A)
for d in commondiv:
    if d > 1 and is_prime(d) and d not in used: ans.append(d)

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

Submission status: Wrong Answer

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-2) + 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: Wrong Answer

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

    if flag:
        answer.append(p)

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

Submission status: Wrong Answer

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

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

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

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

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

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

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

    if flag:
        answer.append(p)

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

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

def poly_divrem_mod(A, B, p):
    d1 = len(A)
    d2 = len(B)
    poly = [a % p for a in A]
    if B[0] != 1:
        inv = pow(B[0], p-2, p)
        B = [(b * inv) % p for b in B]
    while d1 >= d2:
        q = poly[0]
        if q != 0:
            for i, b in enumerate(B):
                poly[i] -= (b*q) % p
                poly[i] %= p
        poly = poly[1:]
        d1 = len(poly)
    return [a % p for a in poly]

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

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

for p in cands:
    if N >= p:
        poly = [0]*p
        poly[0] = 1
        poly[-2] = -1
        rem = poly_divrem_mod(A, poly, p)
    else:
        rem = [a % p for a in A]
    if sum(rem) == 0:
        answer.append(p)

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