You are not logged in. Please login at www.codechef.com to post your questions!

×

APRPS - Editorial

4
3

PROBLEM LINK:

Practice
Contest

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

This question is marked "community wiki".

asked 22 Jul '17, 07:06

deadwing97's gravatar image

3★deadwing97
87827
accept rate: 0%

edited 23 Jul '17, 02:21

admin's gravatar image

0★admin ♦♦
19.6k349497540

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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