DevSkill 23 Another Bigmod Problem

Hints: Just change normal multiplication operation to efficient multiplication operation of UVA 374 Big Mod

Bangla Tutorial of Big Mod:  Big Mod


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

ll bigmul(ll a,ll b,ll m){

    ll result = 0;
    a=a%m;
    while(b)
    {
        if(b%2==1)
        {
            result=(result+a)%m;
        }
        a =(a+a)%m;
        b=b/2;
    }

    return result;
}

long long int bigmod(long long int x,long long int n,long long int m)
{
    long long int y,z;

    if(n==0)
    {
        return 1;
    }
    else if(n%2==0)
    {
        y=bigmod(x,n/2,m);
        return (bigmul(y,y,m));

    }
    else
    {

        z=bigmod(x,n-1,m);
        return(bigmul(x%m,z,m));
    }
}
int main()
{
    long long int x,n,m,t,i,j;
    scanf("%lld",&t);
    for(i=1;i<=t;i++)
    {
        scanf("%lld %lld %lld",&x,&n,&m);
        printf("Case %lld: %lld\n",i,bigmod(x,n,m));
    }

    return 0;

}

Download Coding Interview Book and Get More Tutorials for Coding and Interview Solution: Click Here

Download System Design Interview Book and Get More Tutorials and Interview Solution: Click Here

Do you need more Guidance or Help? Then Book 1:1 Quick Call with Me: Click Here

Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge. Learn More: Click Here