La forma en que abordé este problema es la siguiente:
Deje z ser el número dado. Entonces podemos escribir z como:
[matemáticas] z = 10 * x + y [/ matemáticas]
donde y [matemáticas] \ en [/ matemáticas] [1,9].
Digamos que el número mínimo es de k dígitos donde k> = 40.
Podemos formular la condición mencionada en la pregunta de la siguiente manera:
- Traté de hacer este problema: 1984 - Pesadilla de navegación, pero obtengo TLE. ¿Cómo puedo mejorar mi algoritmo? ¿Cuál es la explicación de esta tarea?
- ¿Qué es un filtro de floración y para qué se utilizan?
- Cómo garantizar un resultado devuelto de la función que llamamos (en sí mismo) es correcto en la recursividad
- ¿Cuál es la relación entre las cadenas de Markov y los procesos de Poisson?
- ¿Cuál es la diferencia entre usar <y <= en la búsqueda binaria?
(10 * x + y) * 9 = y * [matemáticas] 10 ^ {k-1} [/ matemáticas] + x
89 * x = y * ([matemáticas] 10 ^ {k-1} [/ matemáticas] – 9)
Como y no puede dividir 89, entonces ([matemática] 10 ^ {k-1} [/ matemática] – 9) debería dividir 89.
Escribí un código simple de Python para encontrar el valor de k .
para i en xrange (39,100):
if (pow (10, i) – 9)% 89 == 0:
potencia = i
descanso
poder de impresión
El bucle se rompe a la potencia = 43.
Como ambos números (lhs y rhs) tienen los mismos dígitos, el valor de y debería ser 9. x puede calcularse a partir de
x = (y * ([matemáticas] 10 ^ {k-1} [/ matemáticas] – 9)) / 89
Entonces el número z es
(([matemáticas] 10 ^ {potencia} [/ matemáticas] -9) / 89) * 9 * 10 + 9
Podemos encontrar la solución final como:
imprima “número final es”, ((pow (10, power) -9) / 89) * 9 * 10 + 9
La respuesta que muestra es: 10112359550561797752808988764044943820224719
He verificado la solución:
imprimir 9 * 10112359550561797752808988764044943820224719 == 91011235955056179775280898876404494382022471
imprimir len (“10112359550561797752808988764044943820224719”)
e imprime True y 44. Esto muestra que la solución es correcta y de 44 (> 40) dígitos.
Desde que usé Python no me preocupé mucho por el tipo de almacenamiento. Si tuviera que codificarlo en Java, usaría BigInt Library y en C ++ podría haber creado una plantilla para la división / multiplicación / adición de BigInt o utilizar las otras bibliotecas de BigInt (ver referencias) y vincularlo con mi código para resolver esta pregunta .
Para las bibliotecas C ++ BigInt, consulte : Biblioteca C ++ Big Integer, clase C ++ BigInt
