Big Mod [ Find Mod Answer ]

BigMod Algorithm.cpp

/* Author: Remon Hasan
   Algorithm: BigMod */

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll BigMod(ll base, ll power, ll mod)
{
    if(power==0)
        return 1;

    else if(power%2==1) // if power is odd ( ধরি , 2^3 % Mod) বের করব-> (((2^2)^2)%mod . (2^1)%mod)%mod এভাবে করলে উত্তর পাব  
    {
        int a = base % mod; // a হলো (2^1)%mod)
        int b = (BigMod(base,power-1,mod))%mod; // b হলো (((2^2)^2)%mod
        return (a*b)%mod; // উত্তর হলো (((2^2)^2)%mod . (2^1)%mod)%mod
    }
    else if(power%2==0) // if power is even
    {
        int a = (BigMod(base,power/2,mod))%mod;
        return (a*a)%mod;
    }
}

int main ()
{

    ll base,power,mod;
    cin>>base>>power>>mod;
    cout<<BigMod(base,power,mod)<<endl;
    return 0;
}