C Program to find the result of a Number raised to another Number in Modulo (10 ^ 9) + 7 (For Large Integers) (Recursive approach)

 

// Program by Akash Tripathi (@proakash256) 

 

// The remainder obtained after the

// division (%) operation on two operands

// is known as Modulo Operation.

// The reason for taking mod is to prevent

// integer overflows.

// The number should be large enough to fit

// in the largest integer data type and it

// should be prime so as to compute 

// the modulo inverse.

// (10 ^ 9) + 7 fulfills both the criteria.

// Some properties of modulo are :

// 1. (a + b) % M = ((a % M) + (b % M)) % M;

// 2. (a * b) % M = ((a % M) * (b % M)) % M;

// 3. (a - b) % M = ((a % M) - (b % M) + M) % M;

// 4. (a / b) % M = ((a % M) * ((b ^ -1) % M)) % M;

// To find :- (a ^ b)

// Here both a and b are Integers

#include <stdio.h>

long long power(long long c , long long d , int M)

{

    static long long res = 1;

    if (d > 0)

    {

        if ((d & 1) != 0) // (d % 2) != 0 (Condition for Odd)

        {

            res = ((res % M) * (c % M)) % M;

        }

        power((((c % M) * (c % M)) % M) , (d >> 1) , M);

    }

    return res;

}

// Another Recursive Method :

// long long power(long long c, long long d, int M)

// {

//     if (d == 0)

//         return 1;

//     if (d == 1)

//         return c;

//     long long res = power((((c % M) * (c % M)) % M),

                       (d >> 1), M);

//     if ((d & 1) != 0) // (d % 2) != 0 (Condition for Odd)

//     {

//         res = ((res % M) * (c % M)) % M;

//     }

//     return res;

// }

 

int main()

{

    long long a;

    long long b;

    int M = 1000000007;

    printf("Enter the Number : ");

    scanf("%lli" , &a);

    printf("\nEnter the Power : ");

    scanf("%lli" , &b);

    long long res;

    if(b < 0)

    {

        res = power((1 / a) , (-b) , M);

    }

    else

    {

        res = power(a , b , M);           

    }

    printf("\n(%lli ^ %lli) is : %lli\n\n" , a , b , res);

    return 0;

}