Eldric Liew señaló que solo hay tantos cuadrados perfectos de N dígitos. Eso es cierto, pero hay [math] O (\ sqrt {10} ^ N) [/ math] de ellos, por lo que eso no te ayudará en absoluto.
Supongamos que [math] K = N / 2 [/ math], [math] a, b [/ math] sean dos números de dígitos [math] K [/ math] (permitiendo ceros iniciales en [math] b [/ math ] solamente). Llamaremos a [math] (a, b) [/ math] un par roto si [math] n = 10 ^ K * a + b [/ math] (la concatenación de [math] a [/ math] y [math ] b [/ math]) es un número desgarrado.
Lo primero que noto es que [matemáticas] a = 10 ^ K-2 [/ matemáticas], [matemáticas] b = 1 [/ matemáticas] siempre funciona. Sin embargo, eso no es terriblemente útil a menos que solo necesite un número desgarrado.
- ¿Qué algoritmos se usan para calcular logaritmos?
- Cómo usar un algoritmo rápido para la detección y el seguimiento del objeto anómalo
- Si tuviera los 1 y 0 correctos, ¿podría crear alguna imagen / video posible?
- ¿Cuál es el significado de la simulación de recursividad?
- ¿Qué es un algoritmo numérico simpléctico?
salte al enfoque alternativo para una solución de trabajo mucho mejor.
Así es como comenzaría mi enfoque al tratar de evitar demasiada teoría de números.
[matemáticas] n = 10 ^ K * a + b = (a + b) ^ 2 [/ matemáticas]
Esto nos da una ecuación cuadrática.
Resolverlo (y tomar solo la solución positiva) produce
[matemáticas] b = \ frac {1-2a + \ sqrt {1 + 4 (10 ^ K-1) * a}} {2} [/ matemáticas]
La otra solución sería negativa, por lo que sabemos que cada [matemática] a [/ matemática] tiene como máximo una [matemática] b [/ matemática] con la que se puede combinar.
[math] b [/ math] debe ser un número entero, por lo que si [math] (a, b) [/ math] es un par, entonces
[matemáticas] 1 + 4 (10 ^ K-1) * a [/ matemáticas] es un cuadrado perfecto impar.
[matemática] 1 + 4 (10 ^ K-1) * a = (2m + 1) ^ 2 = 4m ^ 2 + 4m + 1 [/ matemática]
[matemática] (10 ^ K-1) * a = m (m + 1) [/ matemática] para algún número entero [matemática] m [/ matemática]
[matemática] 10 ^ K-1 [/ matemática] es [matemática] 99999… 9 [/ matemática] ([matemática] K [/ matemática] [matemática] 9 [/ matemática] s)
[matemáticas] 10 ^ K-1 = 3 ^ 2 * 111 … 11 = m * (m + 1) [/ matemáticas]
[matemática] 3 [/ matemática] no puede ser un factor de [matemática] m [/ matemática] y [matemática] m + 1 [/ matemática], entonces uno de los dos es divisible por [matemática] 9 [/ matemática] . También puede mostrar que [matemática] ([/ matemática] [matemática] 10 ^ K-1) / 9 \ equiv K \ mod 3 [/ matemática], pero eso solo ayuda en casos especiales.
Además, el lado derecho debe ser par y [matemáticas] 10 ^ K-1 [/ matemáticas] no lo es, así que [matemáticas] a [/ matemáticas] siempre debe ser par.
Por aquí empezamos a quedarnos sin vapor. Podríamos comenzar a trabajar con repunidades, pero eso puede ser un poco complicado.
Incluso con estas restricciones, hay una buena cantidad de verificación por hacer.
En cambio, ofrezco un enfoque alternativo :
Utiliza un poco de teoría de números, pero no está tan mal.
Una vez más, consideramos la ecuación
[matemáticas] 10 ^ K * a + b = (a + b) ^ 2 [/ matemáticas]
Pero esta vez lo consideramos [matemática] \ mod 10 ^ j [/ matemática] para [matemática] j = 1,2,3,…, K [/ matemática]
[matemáticas] \ mod (10 ^ K * a + b, 10 ^ j) \ equiv \ mod (b, 10 ^ j) [/ matemáticas]
[matemáticas] \ mod ((a + b) ^ 2,10 ^ j) \ equiv \ mod (a ^ 2,10 ^ j) + \ mod (2ab, 10 ^ j) + \ mod (b ^ 2,10 ^ j) [/ matemáticas]
Mirando [math] j = 1 [/ math], obtenemos (usando [math] c = \ mod (a, 10), d = \ mod (b, 10) [/ math]
[matemáticas] d = \ mod (c ^ 2 + 2cd + d ^ 2,10) [/ matemáticas]
Los únicos pares posibles [matemática] (c, d) [/ matemática] son
[matemáticas] (0,0), (0,1), (0,5), (0,6), (4,4), (4,9), (8,1), (8,4) , (8,9) [/ matemáticas]
¡Eso es solo 9 posibilidades, en lugar de 100!
Para comprender esto, necesitará aprender un poco sobre cómo resolver la aritmética cuadrática en modular. No es tan difícil como parece y puede hacer que una computadora lo haga fácilmente.
Luego usamos esa información para resolver el módulo [matemáticas] 100 [/ matemáticas] y luego [matemáticas] 10 ^ 3 [/ matemáticas], y [matemáticas] 10 ^ 4 [/ matemáticas], etc.
En [matemáticas] 10 ^ 4 [/ matemáticas], solo hay 37 posibilidades.
Haga esto hasta [matemática] 10 ^ K [/ matemática] y tendrá todas las soluciones posibles mucho más rápidamente que la verificación de fuerza bruta.
Sin embargo, no estoy exactamente seguro de cuál es el tiempo de ejecución, así que no puedo prometer nada.
