C. Primitive Primes (Codeforces CodeCraft-20 Div. 2)

この問題の証明にはちょっと感動しました。

問題

https://codeforces.com/contest/1316/problem/C

問題概要

次の多項式と、次の多項式が与えられる。どちらも原始多項式（係数の累積GCDが1）である。また、素数が与えられる

二つの多項式の積の個の係数で、で割り切れないものの次数を一つ答えよ。

考察

私の数学力および文章力ではこの感動を伝えきれませんので、いきなりリンクを貼ってしまいますが

原始多項式とその積について | 高校数学の美しい物語

ずばり、このページの後半部分、ガウスの補題の証明がそのまんまこの問題の証明となります。

よって、このページでいうところの（というか）が答えです。

感想

こういう問題を見ると、数学やり直したくなります。