El número con la propiedad de rotación a la derecha tiene la forma:
ABCD y DABC = k * ABCD
Podemos ver fácilmente que k debería ser menor que 10, porque si k es mayor que 10, k * ABCD tendrá más dígitos que ABCD.
- ¿Cómo se mejora un algoritmo de aprendizaje automático basado en la experiencia?
- Cómo encontrar el número máximo de árboles de expansión mínima en un gráfico
- ¿Qué tan difícil es la entrevista de Google? ¿Qué tipo de algoritmos y preguntas de ingenio espero?
- ¿Cómo podemos decir que la búsqueda binaria es un algoritmo rápido?
- No entiendo las torres recursivas del problema de Hanoi. ¿Qué es?
Para cada número de k de 1 a 9, y con el dígito más significativo (MSD) es a, a de k a 9, podemos encontrar el número mínimo X que satisface X / k es la rotación izquierda de X, y X tiene su MSD es a.
Pseudocódigo:
para (int k = 1; k <10; k ++) {
para (int a = k; a <10; a ++) {
largo X = 0;
int cur = a;
int mod = 0;
hacer{
X = X * 10 + cur;
cur = (mod * 10 + cur) / k; // El resultado de esta división es el siguiente dígito de X
mod = (mod * 10 + cur)% k;
if (par visto anteriormente)
rotura;
} while (cur! = a && mod! = 0);
// Tenga en cuenta que iteraremos menos de 100 pasos, ya que solo hay un valor 10 * 10 de par (cur, mod).
}
}
Notamos que, todo número Y <10 ^ 100 que Y / k es la rotación izquierda de Y tendrá la forma XXXXXX …
Entonces, el trabajo ahora es simple, ya que cada Y terminará con X, solo mantenga los últimos 5 dígitos de X y multiplique por la cantidad de números Y válidos (= 100 / número de dígitos de X).
Suma todos esos 5 dígitos, obtendremos la respuesta para este problema.
Desde aquí: Proyecto Euler # 168
