Editorial for Buen Equipo

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: aniervs

Definamos $A(n) = \sum_{i = 1}^n \lfloor\sqrt[3]{i} \rfloor$ y $B(n) = \sum_{i = 1}^n \lceil\sqrt[2]{i} \rceil$ . Ła respuesta sería $A(n) + B(n)$ ~A(n) + B(n)~.

Veamos primero cómo calcular $A(n)$ ~A(n)~. Notemos que para cada $i \in [a^3; (a + 1)^3)$ ~i \in [a^3; (a + 1)^3)~, se cumple que $\lfloor\sqrt[3]{i}\rfloor= a$ ~\lfloor\sqrt[3]{i}\rfloor= a~. Por tanto, podemos iterar entre cada par de cubos consecutivos $(a^3, (a+1)^3)$ ~(a^3, (a+1)^3)~ y añadir la raíz cúbica del menor de cada uno ( $a$ ~a~) tantas veces como números hay entre ellos. Debemos tener cuidado en el último par de cubos, cuando el límite superior supera $n + 1$ ~n + 1~.

La misma idea se puede aplicar para calcular $B(n)$ ~B(n)~. En este caso, para cada $i \in (a^2, (a+1)^2]$ ~i \in (a^2, (a+1)^2]~ se cumple que $\lceil\sqrt[]{i}\rceil = a+1$ ~\lceil\sqrt[]{i}\rceil = a+1~. Por tanto podemos iterar por cada par de cuadrados consecutivos y añadir la raíz cuadrada del mayor de cada uno tantas como números hay entre ellos. Aquí debemos tener cuidado cuando el límite superior de cada rango supera a $n$ ~n~.

Con todo lo anteriormente dicho:

$\displaystyle A(n) = \sum_{i = 1}^{\lfloor\sqrt[3]{n}\rfloor} \left(min(n+1,(i+1)^3) - i^3\right)\cdot i$

$\displaystyle B(n) = \sum_{i = 0}^{\lfloor\sqrt{n}\rfloor} \left(min(n, (i+1)^2) - i^2\right)\cdot (i+1)$

La complejidad temporal está dominada por cómo calculamos $B(n)$ ~B(n)~, ya que $\sqrt{n} \ge \sqrt[3]{n}$ ~\sqrt{n} \ge \sqrt[3]{n}~. Entonces sería $\mathcal{O}(\sqrt{n})$ ~\mathcal{O}(\sqrt{n})~.

Código de ejemplo:

#include<bits/stdc++.h>
using namespace std;


long long sq(long long x){ return x * x; }
long long cub(long long x){ return x * x * x; }

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    long long n;
    cin >> n;
    long long a = 0, b = 0;

    for(long long i = 1; cub(i) <= n; i++)
        a += i * (min(n + 1, cub(i + 1)) - cub(i));
    for(long long i =  0; sq(i) <= n; i++)
        b += (min(n, sq(i+1)) - sq(i)) * (i + 1);
    cout << a + b;

    return 0;
}

Comments

9
karellgz commented on July 31, 2023, 5:23 a.m. ← edited →
Hi, el problema tambien puede ser resuelto en $O(1)$ ~O(1)~ utilizando una formula (esta mas abajo), para llegar a ella hay que analizar: Te piden la suma de todos los elementos de un arreglo $a$ ~a~, donde cada posicion $a_i$ ~a_i~ contiene $\lceil \sqrt i \rceil + \lfloor \sqrt[3] i \rfloor$ . En otras palabras, la solucion es: $\displaystyle S = \sum _{i=1} ^ {N} {a_i} = \sum _{i=1} ^{N} {(\lceil \sqrt i \rceil + \lfloor \sqrt[3] i \rfloor)}$ Lo que nos permite analizar por separado: $\displaystyle \sum _{i=1} ^{N} \lceil \sqrt i \rceil + \sum _{i=1} ^{N} {\lfloor \sqrt[3] i \rfloor}$

La parte de $\lceil \sqrt i \rceil$ ~\lceil \sqrt i \rceil~

Si se observa la grafica o solamente los valores va a aparecer algo asi: $1,2,2,2,3,3,3,3,3,4...$ ~1,2,2,2,3,3,3,3,3,4...~ Osea los numeros se van a ir repitiendo. Pero se van a ir repitiendo segun un patron, el 1 se repite 1 vez, el 2 se repite 3 veces, y asi, al N-esimo numero se repite $2N-1$ ~2N-1~ veces (es sencillo demostrarlo). Siguiendo con la idea, necesitamos sumarlos: $\displaystyle \sum _{i=1} ^{M} {i(2i - 1)} = \sum _{i=1} ^{M} {(2i^2 - i)} = 2 \sum _{i=1} ^{M} {i^2} - \sum _{i=1} ^{M} {i} =$ $\displaystyle = \frac {M(M+1)(2M+1)} {3} - \frac {M(M+1)} {2} = \frac {M(M+1)(4M-1)} {6}$ Donde $M$ ~M~ es la raiz del cuadrado inmediatamente inferior a N, osea $\lfloor \sqrt N \rfloor$ ~\lfloor \sqrt N \rfloor~, por lo que nos falta sumarle el intervalo que se nos queda $...+(N - M^2 )(M + 1)$ ~...+(N - M^2 )(M + 1)~ Y con eso listo por esta parte.

La parte de $\lfloor \sqrt[3] i \rfloor$ ~\lfloor \sqrt[3] i \rfloor~

Procedemos igual que en el paso anterior, los valores son $1,1,1,1,1,1,1,2,2,2...$ ~1,1,1,1,1,1,1,2,2,2...~, hay $3n^2 + 3n + 1$ ~3n^2 + 3n + 1~ numeros N (no confundir con $N$ ~N~, de la entrada), puedes comprobarlo si quieres, luego: $\displaystyle \sum _{i=1} ^{M_c} (3i^2 + 3i + 1)i = \sum _{i=1} ^{M_c} (3i^3 + 3i^2 +i) =$ $\displaystyle = \frac {3M_c^2(M_c+1)^2} {4} + M_c(M_c+1)^2$

Con $M_c=\lfloor \sqrt[3] {N+1} \rfloor - 1$ . Y agregamos lo que nos quedaba al igual que ahorita: $...+(M_c+1)(N+1-(M_c+1)^3)$ ~...+(M_c+1)(N+1-(M_c+1)^3)~. Y listo, juntando todo hasta aca queda la solucion: $\displaystyle S = \frac {M(M+1)(4M-1)} {6} + (N - M^2 )(M + 1) + \frac {3M_c^2(M_c+1)^2} {4} + M_c(M_c+1)^2 + (M_c+1)(N+1-(M_c+1)^3)$ (No sustituyan $M$ ~M~ y $M_c$ ~M_c~ porque da miedo).

Mi codigo:

#include<bits/stdc++.h> using namespace std; typedef long long int ll; /* Funcion Principal. ~k4r3l_dev */ int main(){ //Introducir N ll N; cin>>N; //Calculamos M y Mc ll M = floor(sqrt(N)), Mc = floor(cbrt(N+1)-1); ll res = 0; //La parte de la raiz cuadrada res+= M*(M + 1)*(4*M - 1)/6 + (N - M*M)*(M+1); //La parte de la raiz cubica res+= 3*Mc*Mc*(Mc+1)*(Mc+1)/4 + Mc*(Mc+1)*(Mc+1); res+= (Mc+1)*(N + 1 - (Mc+1)*(Mc+1)*(Mc+1) ); cout<<res; return 0; }

(sorry, tenía un error en la parte de $\lfloor \sqrt[3] x \rfloor$ ~\lfloor \sqrt[3] x \rfloor~, ya lo arreglé cualquier error diganme)