bigmod2

/*
    @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;
}