UVa 10778

From Algorithmist
Jump to: navigation, search

10778 - Mathemagicland[edit]

Summary[edit]

This problem is really asking for all the rational roots of a polynomial with integer coefficients.

Explanation[edit]

To see that we have, for n = 3:
\sigma _{1}=a+b+c
\sigma _{2}=ab+ac+bc
\sigma _{3}=abc

and that a,b,c are the roots of x^{3}-(a+b+c)x^{2}+(ab+ac+bc)x-abc. This holds in general, with the signs alternate between adjacent powers of x, and that the sign of the leading coefficient is 1. Of course, there are a lot of advanced algorithms for factoring, such as Strum's algorithm. But the intent of this problem is just the basics. Recall that you factor stuff in high school using the Rational Roots Theorem and Remainder Theorem. But there is one problem: what happens if there are multiple roots? One idea is to divide the roots out, possibly using Synthetic division. You may also want to avoid using doubles. So how do you achieve synthetic division in this case? We need a simple result from question B1 of the 2004 Putnam Contest. Alternatively, if you know your algebra well enough, Z[x] is a unique factorization domain. Unqiue Factorization is a result of euclidean algorithm, and a root of p(x) is a multiple root if and only if it divides the greatest common divisor of p and its derivative p'.

Input[edit]

2 1
2 1
0

Output[edit]

1 1

References[edit]

  1. Rational Roots Theorem
  2. Remainder Theorem