快速乘法计算模幂

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/44280737

一般的快速模幂可能会产生整数溢出的情况 ，可以用快速乘法解决此问题 。

模板如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>

using namespace std;

long long mult_mod(long long a, long long b, long long c)
{
	a %= c;
	b %= c;
	long long ret = 0;
	long long tmp = a;
	while (b)
	{
		if (b & 1)
		{
			ret += tmp;
			if (ret > c)ret -= c;//直接取模慢很多
		}
		tmp <<= 1;
		if (tmp > c)tmp -= c;
		b >>= 1;
	}
	return ret;
}
long long pow_mod(long long a, long long n, long long mod)
{
	long long ret = 1;
	long long temp = a%mod;
	while (n)
	{
		if (n & 1)ret = mult_mod(ret, temp, mod);
		temp = mult_mod(temp, temp, mod);
		n >>= 1;
	}
	return ret;
}

int main()
{
	long long a, n, mod;
	while (scanf("%lld%lld%lld", &a, &n, &mod) != EOF)
	{
		printf("%lld\n",pow_mod(a,n,mod));//a^n%mod
	}
}