a^b%c 小技巧

我们知道像a^b这样的数在计算的时候因为大的增长速度很快，所以经常越界，所以很多题目在出的时候都会让我们取模。

a^b = a*a*a*a……（一共b个a相乘）；我们前一篇文章在说两个数相乘的时 ，如果两个数足够大的话，这两个数相乘就会越界，使计算结果出错。所以我们在来写a^b时应该先写出两个数相乘的计算方法。

这个就不多说了，上一篇文章中有在这只是贴出代码。

__int64 mult_mod(__int64 a,__int64 b,__int64 c)
{
	a=a%c;
	b=b%c;
	__int64 ans=0;
	while(b)
	{
		if(b&1) {   ans+=a; ans=ans%c;}
		a<<=1;a%=c;
		b>>1;
	}
	return ans;
}

我们在处理它时同样适用二进制和位运算来处理所以我说二进制和位运算是很重要的嘛。

__int64 pow_mod(__int64 a,__int64 b,__int64 c)
{
	a=a%c;
	__int64 ans=1;
	while(b)
	{
		if(b&1) 
		{   
			ans =mult_mod(ans,a,c);
			ans%=c;
		}
		a=mult_mod(a,a,c);
		b>>1;
	}
	return ans;
}

好了。

感谢自己坚持。

a^b%c 小技巧,布布扣,bubuko.com

a^b%c 小技巧

原文：http://blog.csdn.net/u010123208/article/details/25393067