### PROBLEM LINK:

**Author:** Trung Nguyen

**Primary Tester:** Misha Chorniy

**Editorialist:** Hussain Kara Fallah

### DIFFICULTY:

Hard

### PREREQUISITES:

Advanced Math,FFT,Number Theoretical Transforms

### 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.

### EXPLANATION:

### 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:

**Subtask 1:**

Using paper.

**Sub task 2:**

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.

**Sub task 3:**

.

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.

Subtask 4:

Expanding f(x + \sqrt{x_i}) to A(x) + \sqrt{x_i} * B(x) by FFT.

To deal with modulo 10^9 + 7, we can use NTT with three large prime or **Karatsuba** (not intended), and normal FFT with \sqrt{mod} technique. You can see in Author, tester solution

### AUTHOR’S AND TESTER’S SOLUTIONS:

**AUTHOR’s solution**: Can be found here

**TESTER’s solution**: Can be found here