PROBLEM LINK:Author: Trung Nguyen DIFFICULTY:Hard PREREQUISITES:Advanced Math,FFT,Number Theoretical Transforms PROBLEM:It is wellknown that $\sum_{}^{}\sqrt{a_i}$ where $a_i \in \mathbb{N}$ is a root of some integercoefficient 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:TheoremLet $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 integercoefficient 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 freesquare 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 integercoefficient. This is easy to see by following recursive formula: Subtask 1: Using paper. Sub task 2: There are at most $2^n$ freesqure induce from n prime. So represent each coefficent in the form of $2^n$ freesquare 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
This question is marked "community wiki".
asked 22 Jul '17, 07:06
