Directly calculate \(pow(a,b)\) is \(O(b)\). It is trivial. We can use repeated squaring to solve it efficiently as \(O(lgb)\), that is to say, divide \(b\) into several power of \(2\). And calculate \(pow(a,2^i)\) and sum them.

For example, \(a^{11}=a^{2^0}\times a^{2^1}\times a^{2^3}\).

Sometimes we want to get the modular exponentiation. The solution is based on the formula.

$$((a\ mod\ p)(b\ mod\ p))\ mod\ p=(ab)\ mod\ p$$

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

int Exponentiation(int a, int b)
{
	int res = 1;
	while (b > 0)
	{
		if (b & 1) res = res * a;
		b = b >> 1;
		a = a * a;
	}
	return res;
}

int ModularExponentiation(int a, int b, int n)
{
	int res = 1;
	a = a % n;
	while (b > 0)
	{
		if (b & 1) res = (res*a) % n;
		b = b >> 1;
		a = (a*a) % n;
	}
	return res;
}

int main()
{
	int a, b, n;
	scanf("%d %d %d", &a, &b, &n);
	printf("%d\n",Exponentiation(a, b));
	printf("%d\n",ModularExponentiation(a, b, n));
	system("pause");
	return 0;
}

Result:

2 5 13
32
6

Reference

[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.

[2] https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/

[3] http://www.cnblogs.com/CXCXCXC/p/4641812.html

Leave a Reply

Your email address will not be published. Required fields are marked *