Coding Problems & Solution ( HackerEarth: Basic Number Theory - 1)

This problem was posted by HackerEarth.

Problem Statement:

Find the answer of $\left(\frac{A^B}{C}\right)\%M$.

Input :

TThe only line of input consists of four integers A, B, C and M. The input always has C and M such that gcd(C, M)=1.

Output :

Print the answer as asked in the problem statement.

Constraints :

$1\le A,B,C,M\le {10}^9$
$gcd(C,M)=1$.

Sample Input 0

2 3 4 5

Sample Output 0

2

Solution

	#include <iostream>
	using namespace std;
	// C function for extended Euclidean Algorithm
	int gcdExtended(int a, int b, int *x, int *y);
	int modInverse(int a, int m)
	{
	int x, y;
	int g = gcdExtended(a, m, &x, &y);
	if (g != 1){
	cout << "Inverse doesn't exist";
	return -1;
	}
	else
	{
	// m is added to handle negative x
	int res = (x%m + m) % m;
	return res;
	}
	}
	// C function for extended Euclidean Algorithm
	int gcdExtended(int a, int b, int *x, int *y)
	{
	// Base Case
	if (a == 0)
	{
	*x = 0, *y = 1;
	return b;
	}
	int x1, y1; // To store results of recursive call
	int gcd = gcdExtended(b%a, a, &x1, &y1);
	// Update x and y using results of recursive call
	*x = y1 - (b/a) * x1;
	*y = x1;
	return gcd;
	}
	/* This function calculates (ab)%c */
	int modulo(int a,int b,int c){
	long long x=1,y=a; // long long is taken to avoid overflow of intermediate results
	while(b > 0){
	if(b%2 == 1){
	x=(x*y)%c;
	}
	y = (y*y)%c; // squaring the base
	b /= 2;
	}
	return x%c;
	}
	int main()
	{
	int a=0, b=0, c=0, m=0;
	cin >> a >> b >> c >>m;
	long long cal1 = (modInverse(c,m)%m);
	long long cal2 = (modulo(a,b,m) %m);
	long long cal = (cal1 * cal2)%m;
	printf("%lld", cal);
	return EXIT_SUCCESS;
	}

view raw NumberTheory_1.cpp hosted with ❤ by GitHub