En el articulo anterior te ensene como sacarle el Máximo Común Divisor a dos números uno extremadamente grande y el otro aceptable en una variable. Si Deseas puedes mirarlo Aqui.
Pero no siempre sucede que tendremos el numero exacto para operarlo, que pasaría si nuestro numero muy grande a operar es del tipo a^b por ejemplo 2^100 tiene 31 dígitos entonces aquí también tenemos un problema que para lograr operar esa exponenciacion no podremos almacenar dicho valor en una variable de números entonces aquí también surge una solución.
Usar El Paradigma Divide Y Vencerás
supongamos que nuestros numero grande es a^b, y nuestro numero pequeño N.
Similarmente al ejercicio anterior este problema se resuelve haciendo uso del BIGMOD, sacandole el modulo a N y esta operación ingresandola de esta manera en el MCD(N,MOD(a^b,N)). Como explique en el articulo anterior esto es posible por la congruencia de numeros. Volviendo a nuestra explicación, el problema como podemos observar es operar MOD(a^b,n), ya que no es posible hacerlo por que a^b es muy grande para almacenarlo entonces hay que dividir a^b en dos numeros por ejemplo a^b=a^(b/2)×a^(b/2) y esta operacion con modulo n, a la siguiente vuelta divirdirlo en otras mitades y asi sucesivamente hasta que el numero sea del tipo a^1 modulo n, y ahi recien podremos operar. esta solucion es recursiva.
Aqui te muestro un ejemplo mas claro
Implementacion en C++:
Igualmente tmbn este ejercicio pertenece a la UVA que es una pagina web donde se publican los ejercicios que vinieron en los concursos de la ACM ICPC y tambien se proponen ejercicios nuevos.
Espero te haya gustado este articulo, si es asi me ayudarias bastante difundiendo mi blog. Gracias.
SOCIALIZA ESTO →