 # APRPS - Editorial

Author: Trung Nguyen
Primary Tester: Misha Chorniy
Editorialist: Hussain Kara Fallah

Hard

### PROBLEM:

It is well-known that \sum_{}^{}\sqrt{a_i} where a_i \in \mathbb{N} is a root of some integer-coefficient polynomial. Given n distinct prime numbers. Now, your task is to find not only such polynomial but also the minimal one such that \sum_{i=1}^{i=n} \sqrt{a_i} is a root of this polynomial. When comparing two polynomials, firstly, we consider their degree and then the coefficient of the highest term, and then the second highest term and so on.

### Theorem

Let x_1,x_2,x_3....x_n be n distinct square free integers. Then if a_1,a_2,a_3,....a_n are rational numbers such that:

\sum_{i=1}^{i=n} a_i * \sqrt{x_i} = 0

Then:

a_i = 0 \ for\ any\ (1\leq i \leq n) You can find the proof here.

Assume f(x) is integer-coefficient polynomial with root \sqrt{x_1} + \sqrt{x_2} + \sqrt{x_3} + ... \sqrt{x_n}

Lemma 1:
f(x) is sum of terms, each term is in the form: K * \sqrt{D}, where K is an integer, D is free-square integer (product of some primes).

Lemma 2:

Changing any term +\sqrt{x_i} to -\sqrt{x_i} will result in changing sign of some above terms.
Using above theorem, we obtain that all K coefficients in the Lemma 1 must be 0.

From Lemma 2, we see that f(x) will have 2^n roots.

All roots are following the form: \sum_{}^{} sign_i * \sqrt{x_i} AND sign_i = -1 \ or\ +1

Lemma 3:

The polynomial of degree 2^n with 2^n above roots is integer-coefficient.

This is easy to see by following recursive formula:

Using paper.

There are at most 2^n free-squre induce from n prime. So represent each coefficent in the form of 2^n free-square is easy to pass.

.
Let’s denote by f_i(x) the sought polynomial which has \sum_{k=1}^{k=i} \sqrt{x_k} as a root. It’s clear that:

f_{i+1}(x) = f_i(x + \sqrt{x_{i+1}}) * f_i(x - \sqrt{x_{i+1}})

It is a sought polynomial which has the roots of f_i(x) shifted by +\sqrt{x_i{+1}} and also the roots of f_i(x) shifted by -\sqrt{x_i{+1}}. Having 2^{i+1} roots.

f_{i+1}(x) = f_i(x + \sqrt{x_{i+1}}) * f_i(x - \sqrt{x_{i+1}})

f_i(x + \sqrt{x_{i+1}}) = A(x) + \sqrt{x_{i+1}} * B(x)

f_i(x - \sqrt{x_{i+1}}) = A(x) - \sqrt{x_{i+1}} * B(x)

f_{i+1}(x) = (A(x) + \sqrt{x_{i+1}} * B(x)) * (A(x) - \sqrt{x_{i+1}} * B(x))

f_{i+1}(x) = A^2(x) - x_{i+1} * B^2(x)

Now will need to expand f_i(x + \sqrt{x_{i + 1}}) to A(x) + \sqrt{x_{i + 1}} * B(x).
Then multiply polynomials to get A^2(x), B^2(x).

the naive way O(n^2) easy to get 60 points.