Блог пользователя SmallGirl

Someone really needs your help!
Автор SmallGirl, история, 8 лет назад, По-английски

Hello everyone,

I was solving the last problem from the last CF Round! http://mirror.codeforces.com/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! :)

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

This is because of the factor theorem.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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)

→ Ответить