Tenka1 Programmer Contest 2019 E Polynomial Divisors

面白かったので。
解けてもおかしくなかった。めっちゃ苦戦したけど。

問題はこれ
E - Polynomial Divisors。

ポイントはフェルマーの小定理と、 $N$ 次方程式の根の個数。

解説の準備

フェルマーの小定理

$p$ を素数とする。任意の $p$ の倍数でない整数 $x$ に対して、

$x^p = 1\, mod\, p$

となる。

以下、 $\mathbb{Z}/p\mathbb{Z} = \{0 \, mod\, p , \ldots, p-1\, mod\, p\}$ とかく。

群論を使った簡単な証明：

$|(\mathbb{Z}/p\mathbb{Z})^\times| = p-1$ と「有限群の各元の位数は、その群の位数の約数」から従う。

$N$ 次方程式の根は高々 $N$ 個以下

整域ならよい。つまり、普通に思いつくものはだいたいよい。

解説

$p$ を素数とする。
$f(x) = \sum_{i=0}^N a_i x^i$ とする。
ただし、 $a_N \neq 0$ とする。

$p \geq N+1$ のとき

任意の $i$ に対して、 $A[i$ %p = 0] であればよい。

というのも、 $N$ 次方程式は、 $\mathbb{Z}/p\mathbb{Z}$ 内に高々 $N$ 個しか根を持たないが、
$\mathbb{Z}/p\mathbb{Z}$ の元の個数は、 $p$ 個なので、
$f$ は、恒等的に $0$ でなければならない。

今回は、 $a_N$ が $0$ でないことを使って、その約数を見ることにする。

$p \leq N$ のとき

上の場合の条件でも、もちろん成立する。
今からの議論はその場合も含む。

まず、
$f$ が $x$ を因子に持たないといけないので、
$a_0 = 0\, mod \, p$ でなければならない。

というわけで、 $a_0 = 0\, mod \, p$ の場合のみを考えれば良い。
つまり、残りの $mod\, p$ で $0$ でない整数 $x$ だけ調べれば良い。

フェルマーの小定理を思い出す。
すると、 $x^{p-1} = 1$ になるので、
$f$ は次のように言い換えて良い。

各 $0 \neq x \in \mathbb{Z}/p\mathbb{Z}$ （ $p$ の倍数でない整数 $x$ ）に対して、

$f(x) = \sum_{i=0}^N a_i x^{i\, mod\, (p-1)} =: g(x)$

となる。

これは、 $(p-2)$ 次方程式なので、根を高々 $(p-2)$ 個しか持たない。
$f$ が $0, 1, \ldots, p-1$ を根に持たなければならない。
$0$ は除外して考えているので、
まとめると、
$g$ は根を少なくとも $(p-1)$ 個持たなければならない。

そういうものは、恒等的に $0$ であるようなものしか存在しない。
というのも、根の数を見れば、矛盾が見える。

ちなみに、
$a_0$ が $0$ でなければ $a_0$ の素因数だけを見ればよいが、
めんどくさいので、 $N$ 以下の素数全てを調べている。

解答

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