×

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

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

This question is marked "community wiki".

87827
accept rate: 0%

19.6k349497540

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,266
×1,322
×864
×331
×229
×110
×7

question asked: 22 Jul '17, 07:06

question was seen: 1,174 times

last updated: 23 Jul '17, 02:21