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! :)
This is because of the factor theorem.
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)