Leetcode - 次方取模

问题

计算 a^b 对正整数 c 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

思路

直接求a^b然后取模肯定不现实，但可以根据取模公式(a^b)%c=((a%c)^b)%c和(a*b)%c=(a%c*b%c)%c拆分计算，同时利用a^(km+n)=(a^m)^k*a^n公式对b进行逐位求次方。

代码(C++)

int n=b.size();
int temp=1;
int base=a%c;
for(int i=n-1;i>=0;i--)
{
	temp=pow(temp,10)%c;	
	temp=(temp*(pow(base,b[i])%c))%c;
}
return temp;

优化：pow函数返回值为double，且数据过大时溢出。根据快速幂算法可以进一步拆分。

快速幂

int qpowmod(int x,int n,int vmod)
{
	int temp=1;
	int base=x%vmod;
	while(n)
	{
		if(n&1)
			temp=(temp*base)%vmod;
		base=(base*base)%vmod;
		n>>1;
	}
	return temp;
}

int main()
{
	int temp=1;
	int base=a%c;
	for(int i=0;i<b.size();i++)		//高位在前
	{
		temp=qpowmod(temp,10,c);
		temp=(temp*qpowmod(base,b[i],c))%c;
	}
	return temp;
}