So recently I was trying to solve this problem 100965F - Polynomial, the following blog contains **spoilers**.

The first approach was trying to represent the polynomial as x * (x + 1) * ... * (x + m — 1) and get the result using divide and conquer and FFT multiplication in which didn't fit in the time limit. So the second approach is to print just the polynomial which will give 0 but only for *x* coprime with *m*, but surprisingly it got accepted.

So how is this correct? and also how the checker for this problem is written?

By CRT, we can consider every prime power in the factorization of

mseparately. Now note that:x^{m}-x^{m - φ(m)}=x^{m - φ(m)}(x^{φ(m)}- 1)If

xis coprime withp, then the right factor is 0. Ifxis not coprime withp, then from the fact thatm- φ(m) is greater than the exponent ofp, then the left factor is 0. So the polynomial is 0 in every point.Thanks for your explanation.

Do you have any idea how the checker could've been written? just interested :D