Dev Skill: Another Bigmod Problem

Problem link: Another Bigmod Problem

In this problem, we are given three integers A, B, C; we need to calculate A^B % C.

Solution: We can calculate it by using modular arithmetic. We know

• (a * b) % c = ( (a % c) * (b % c) ) %c 
• (a + b) % c = ( (a % c) + (b % c) ) %c 
• a^b = a * a^(b-1)

So with this we can write this following code to calculate A^B % C

	#define ll long long
	ll bigmod(ll a, ll b, ll c)
	{
	if(b == 0) return 1;
	if(b % 2 == 0)
	{
	ll x = bigmod(a, b / 2, c);
	x = (x * x) % c;
	return x;
	}
	else
	return (a * bigmod(a, b - 1, c)) % c;
	}

view raw bigmod.cpp hosted with ❤ by GitHub

This algorithm is called classical bigmod algorithm. But in this problem, we still have problem. Look at line 9 : x = ( x * x ) % c;

Here, since c can be as large as 10^18, the value of x can be (10^18 - 1 ). When we multiply x with x, it will overflow. For example, try with input a = 10^18 - 1, b = 2, c = 10^18.

So how do we calculate ( x * x ) % c, without overflowing? We use the same divide and conquer approach like above. But this time we will use addition instead of multiplication. It's called bigmultiplication, we will write the function as following:

	#define ll long long
	ll bigmul(ll a, ll b, ll c)
	{
	if (b == 0) return 0;
	if (b % 2 == 0)
	{
	ll x = bigmul(a, b / 2, c);
	x = (x + x) % c;
	return x;
	}
	else
	return (a + bigmul(a, b - 1, c)) % c;
	}

view raw bigmul.cpp hosted with ❤ by GitHub

So finally our full code would look like this:

	#include <bits/stdc++.h>
	using namespace std;
	#define ll long long
	ll bigmul(ll a, ll b, ll c)
	{
	if (b == 0) return 0;
	if (b % 2 == 0)
	{
	ll x = bigmul(a, b / 2, c);
	x = (x + x) % c;
	return x;
	}
	else
	return (a + bigmul(a, b - 1, c)) % c;
	}
	ll Bigmod(ll a, ll b, ll c)
	{
	if (b == 0) return 1;
	if (b % 2 == 0)
	{
	ll x = Bigmod(a, b / 2, c);
	x = bigmul(x, x, c);
	return x;
	}
	else
	{
	return bigmul(a, Bigmod(a, b - 1, c), c);
	}
	}
	int main()
	{
	int t;
	ll a,b,c;
	scanf("%d",&t);
	for(int tc = 1; tc <= t; tc++)
	{
	scanf("%lld %lld %lld",&a,&b,&c);
	printf("Case %d: %lld\n",tc,Bigmod(a,b,c));
	}
	return 0;
	}

view raw bigmod_bigmul.cpp hosted with ❤ by GitHub