RetiredAmrMahmoud's blog

Doubt about a problem
By RetiredAmrMahmoud, 8 years ago, In English

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?

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +24 Vote: I do not like it

By CRT, we can consider every prime power in the factorization of m separately. Now note that:

xm - xm - φ(m) = xm - φ(m)(xφ(m) - 1)

If x is coprime with p, then the right factor is 0. If x is not coprime with p, then from the fact that m - φ(m) is greater than the exponent of p, then the left factor is 0. So the polynomial is 0 in every point.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks for your explanation.

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

    → Reply