Buen Equipo

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

La selección de IslaGrande que participará en la próxima IOI no para de sorprender a los entrenadores con sus conocimientos en matemáticas. Un día los entrenadores les propusieron una nueva tarea:

Se necesita encontrar la suma de los primeros $N$ ~N~ elementos de la secuencia en la cual el $i$ ~i~-ésimo elemento es igual a la suma de la raíz cuadrada de $i$ ~i~, redondeada al entero superior y la raíz cúbica de $i$ ~i~, redondeada al entero inferior más cercano. Es decir, el $i$ ~i~-ésimo elemento de la secuencia es igual a:

$\displaystyle \lceil\sqrt{i}\rceil\ + \lfloor\sqrt[3]{i}\rfloor$

Fácilmente escribieron los primeros elementos de la secuencia y los sumaron. Pero entonces se preguntaron: ¿cómo tratar el problema si $N$ ~N~ es un número muy grande? En este caso, no es fácil escribir los números.

Después de pensar un poco, resolvieron su tarea aún para valores grandes de $N$ ~N~. Pero ellos desean asegurarse que la respuesta sea correcta antes de mostrársela a los entrenadores, entonces le proponen a usted resolver el problema para comparar los resultados.

Entrada

La única línea de entrada contiene un entero $N (1 \leq N \leq 10^{12})$ ~N (1 \leq N \leq 10^{12})~ — el número de elementos en la secuencia de la cual necesitamos encontrar la suma.

Salida

La salida debe contener solamente un número — la suma de los primeros $N$ ~N~ elementos de la secuencia.

Ejemplos

Entrada 1

Salida 1

Explicación

El primer elemento de la secuencia es $2$ ~2~.

Entrada 2

Salida 2

Explicación

El primer elemento de la secuencia es $2$ ~2~; segundo, tercero y cuarto elementos son iguales a $3$ ~3~.

Comments

7

PedroPabloAB commented on June 3, 2021, 3:08 a.m.

Muy buena explicación, gracias por su ayuda.

0

PedroPabloAB commented on June 3, 2021, 3:04 a.m.

Ok gracias

5

aniervs commented on June 2, 2021, 10:59 a.m.

Se añadió una editorial.

3

PedroPabloAB commented on June 2, 2021, 2:18 a.m.

Sé me ocurrió una idea. Cuando se trata de sqrt(x) los valores se repiten, por ejemplo $\displaystyle 1^2=1, 2^2=4$ $$\displaystyle 1^2=1, 2^2=4$$ por tanto $\displaystyle sqrt(x)$ $$\displaystyle sqrt(x)$$ donde x>1 y x<4 va a ser el mismo valor. Esto tiene una gran ventaja para números muy grande: pues si se tienen varios números entre $a^2$ ~a^2~ y $(a+1)^2$ ~(a+1)^2~ y $a=135674$ ~a=135674~ por ejemplo, para hallar la suma de cada raiz no hay necesidad de hallar la raiz de cada número, solo tendría que multiplicarse esa cantidad de números por la raiz: $((a+1)^2-a^2)*a$ ~((a+1)^2-a^2)*a~.

De manera similar se puede hacer para hallar la suma de raices c'ubicas. Implementé el código, solo tuve algunos problemillas en pocos casos de prueba, pero en general está bien el resultado.