Obtiene el módulo de un Número N concatenado N veces.

Question

No sé si este es el foro adecuado.

¿Existe una aproximación matemática para obtener el módulo de un número N que se concatena N veces?

Hoy he tenido el siguiente escenario en una entrevista para un trabajo de desarrollador, esta fue una de las preguntas, y la única que no pude responder.

Concatena el número N N veces y luego calcula su Módulo por 2017.

Por ejemplo para N=5 el número será 55555 y el resultado será Mod(55555,2017) = 1096 para N=10 el número será 101010101010101010 y el resultado Mod(101010101010101010,2017) = 1197

Ahora el número que tenía que calcular era 58184241583791680. La única pista que obtuve fue que el resultado de 58184241583791680 concatenado 58184241583791680 veces el módulo 2017 es un número de 4 dígitos.

Mi pregunta es: ¿Podemos reducir de alguna manera este número o la única solución es concatenar 58184241583791680 veces?

Answer 1

La concatenación de $K$ copias de $N$ es igual a:

$\sum\limits_{i=0}^{K-1}(10^{L\times i}N)$ donde $L$ es el número de dígitos de $N$ . Esto se debe a que se puede considerar que cada copia añade $N$ con algunos ceros a la derecha.

Podemos reescribir esto como: $N\times \sum\limits_{i=0}^{k-1}10^{L\times i}=N\times(10^{L\times K}-1)\times (10^L-1)^{-1}\equiv N\times(10^{L\times K}-1)\times(10^L-1)^{MOD-2}$ (dado que el $MOD$ es primo, que es el caso de $2017$ )

complejidad: $\mathcal O(\log(L)+\log(K)+\log(MOD))$