Contando cuadrados en un rango

Question

He estado trabajando en una serie de desafíos de programación para mejorar mis habilidades matemáticas, y me encontré con una solución que no sé cómo explicar.

El problema:

"Para 1 <= A <= B <= 10^9, encuentra la cantidad de cuadrados perfectos entre $A$ y $B$ (inclusive).

Mi solución inicial fue recorrer todos los números en un rango y contar los cuadrados perfectos de esa manera. Sin embargo, esta fue claramente una solución muy lenta (~ 14 segundos para el rango 1 -> 10^9).

Luego, encontré lo siguiente:

"La cantidad de cuadrados entre $A$ y $B$ = sqrt(B) - sqrt(A - 1) redondeado hacia abajo".

NOTA: Según una respuesta a esta pregunta, redondeado hacia abajo es incorrecto en este caso, pero esta fórmula sirve para encontrar los cuadrados perfectos en un rango dado. El código para esta pregunta en realidad convierte el valor a un int, que realiza el redondeo al número entero más cercano, no necesariamente hacia abajo.

Esto es genial y ofreció una solución mucho más rápida, pero no entiendo por qué.

¿Alguien puede ayudarme a entender por qué esta ecuación simple realmente funciona?

Answer 1

Presumo que $A$ y $B$ son enteros positivos. El número de cuadrados $\le B$ es $\lfloor \sqrt{B} \rfloor$. El número de cuadrados $< A$ es el número de cuadrados $\le A-1$, y por lo tanto $\lfloor \sqrt{A-1}\rfloor. La cantidad entre $A$ y $B$ (inclusive) es la diferencia entre estos.

EDITAR: Pero esto no es lo mismo que "sqrt(B) - sqrt(A - 1) redondeado hacia abajo". Por ejemplo, toma $A = 3$, $B = 4$. Hay un cuadrado ($4$) entre $A$ y $B$, inclusivos, pero $\lfloor \sqrt{4} - \sqrt{2}\rfloor = 0$.

Answer 2

Para entender por qué esta es la respuesta, comencemos con un ejemplo más simple. Echemos un vistazo al número de cuadrados perfectos entre $0$ y $B$. Además, asumamos que $B$ es un cuadrado perfecto, lo que significa que existe un $C$ tal que $C^2=B.

¿Cuántos cuadrados perfectos hay entre $0$ y $B$? Hay exactamente $C$ - para cada entero de 1 a $C$ tenemos un número cuadrado.

Ahora asumamos que $B$ está entre $C^2$ y $(C+1)^2$. ¿Cuántos números cuadrados hay entre $0$ y $B$ esta vez? Definitivamente tenemos $C$ números, ya que $C^2 < B. El número $C+1$ es demasiado grande, sin embargo, para contribuir al total. Eso nos deja con exactamente $C$ cuadrados perfectos. Notemos que $\sqrt B\in(C, C+1)$, de lo cual $\lfloor \sqrt B \rfloor = C.

Entonces ahora volvemos a la pregunta original: sabemos que de $0$ a $A$ tenemos $\lfloor \sqrt A \rfloor$ cuadrados perfectos. De $0$ a $B$ tenemos $\lfloor \sqrt B \rfloor$ cuadrados perfectos. Así que de $A$ a $B$ tenemos tantos como hay de $0$ a $B$ menos tantos como hay de $O$ a $A-1$(debido al hecho de que estamos interesados en los cuadrados perfectos entre $[A,B]$) - eso es, $\lfloor \sqrt B \rfloor - \lfloor \sqrt(A - 1) \rfloor.