SmallGirl's blog

Someone really needs your help!
By SmallGirl, history, 9 years ago, In English

Hello everyone,

I was solving the last problem from the last CF Round! http://codeforces.net/contest/676/problem/E

I can't understand why at the end of the game if P(k) = 0 then the human wins, I mean why if P(k) = 0 then it means that the polynomial P(x) is divisible by polynomial Q(x)?

I really need your help! :)

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

»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

This is because of the factor theorem.

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Suppose it does not.

P(X) = Q(X)·A(X) + B(X) where B(x) is a constant (we have just divided it by using divison with remainder)

Let's now evaluate P(K). We know that P(K) is equal to zero, meaning that:

0 = Q(K)·A(K) + B(K)

Q(K) = 0, because of that we also know that B(K) = 0

But B(X) is a constant polynomial, so the only way B(K) could be equal to zero is when B(X) = 0.

Meaning that when we were dividing P(X) by Q(X) in the first place, remainder was zero, so P(X) is divisible by polynomial Q(X)

→ Reply