/*
@Author : Joel Fernandez
@Web : Codebotic.blogspot.com
@Fecha : 29/06/2015
@Tema : MCD usando Bigmod para numeros con exponentes
*/
#include<iostream>
#include<cstdlib>
using namespace std;
int bigmod(int a, int b, int n)
{
int x;
if(b==0)
return 1;
if(b%2==1)
return((a%n)*bigmod(a,b-1,n))%n;
else
{
x=bigmod(a,b/2,n);
return((x%n)*(x%n))%n;
}
}
int mcd(int a, int b )
{
if(b==0) return a;
else mcd(b,a%b);
}
int main()
{
system("color 0a");
int a,b,n,c;
cout<<"\\t ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»"<<endl;
cout<<"\\t º º"<<endl;
cout<<"\\t º Algoritmo BigMod para Numeros con Exponente º"<<endl;
cout<<"\\t º º"<<endl;
cout<<"\\t ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ "<<endl;
cout<<endl<<endl;
cout<<"\\t Ingrese a:";
cin>>a;
cout<<"\\t Ingrese b:";
cin>>b;
cout<<"\\t Ingrese n:";
cin>>n;
c=bigmod(a,b,n);
cout<<"\\t El modulo de (a^b,n)="<<c<<endl;
cout<<"\\t El Maximo Comun Divisor de(a^b,n)="<<mcd(n,c)<<endl;
return 0;
}