374 Big Mod
http://acm.uva.es/p/v3/374.htmlSe emplea un algoritmo de exponenciacion modular para poder elevar b^p mod m.
Trabajamos con el exponente en binario.
Se lee la posicion mas a la derecha del exponente.
Si el exponente tiene un 1,se multiplica por el modulo m de la base elevada a la posicion que nos encontremos en el exponente.
Si tiene un 0 en el exponente, no hacemos nada.
Tras esto desplazamos el exponente una posicion y para manterne la base elevada a la posicion, tras cada movimiento la elevamos al cuadrado y le aplicamos modulo m.
s=1; t=b; u=p;
while(u) {
if (u&1)
s=(s*t)%n;
u>>=1;
t=(t*t)%n;
}
Donde b es la base, p el exponente y n el modulo.
Portal
Suscribete
Programación
