E - Polynomial Divisors Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

N 次の整数係数多項式 f(x)=a_Nx^N+a_{N-1}x^{N-1}+...+a_0 が与えられます。任意の整数 x に対して p が f(x) を割り切るような素数 p をすべて求めてください。

制約

  • 0 \leq N \leq 10^4
  • |a_i| \leq 10^9(0\leq i\leq N)
  • a_N \neq 0
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

N
a_N
:
a_0

出力

任意の整数 x に対して p が f(x) を割り切るような素数 p を小さい順にすべて出力せよ。

入力例 1

2
7
-7
14

出力例 1

2
7

2,7 は例えば、f(1)=14 や f(2)=28 を割り切ります。

入力例 2

3
1
4
1
5

出力例 2




条件を満たす素数がない場合もあります。














入力例 3
0
998244353













出力例 3
998244353







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