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