[C++知识库]JOE的算数（快速幂算法实现）

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

　　有一天，JOE终于不能忍受计算a^b%c这种平凡的运算了。所以他决定要求你写一个程序，计算a^b%c。

　　提示：若b为奇数,，a^b=(a^(b/2))^2*a，否则a^b=(a^(b/2))^2。

输入格式

　　三个非负整数a,b,c；

输出格式

　　一个整数ans，表示a^b%c；

样例输入

7 2 5

样例输出

4

数据规模和约定

　　30% a <= 100, b <= 10^4, 1 <= c <= 100
　　60% a <=10^4, b <= 10^5, 1 <= c <= 10^4
　　100% a <=10^6, b <= 10^9, 1 <= c <= 10^6

思路：用快速幂算法实现，结合数学公式（a*b）%c=（a%c*b%c）%c，所以，a与b的乘积再取模，可以拆开，其中a与b还可以看为1，则a%c=a%c%c(b%c=b%c%c).

快速幂算法:由于指数爆炸，当指数足够大时会溢出，尽管是long long的范围也会溢出，而且还会增加循环的次数，比如2的100次方，需循环100次，而2得100次方写成4^50=16^25=256^12*16。（n为奇数时，拆成上一次的底数*扩大的底数的偶次方）

经过更少的循环，让指数不断除以2,而底数扩大为自身的平方，最后，指数n变为1，将扩大后累计的底数赋值给输出结果，最后退出循环。（如下所示）

由于位操作更快,得以终极优化。

n&1 (n%2==1）

n>>1(n/=2)

n<<1(n*=2)

#include<stdio.h>
int main(void)
{
	 long long  m, n, c;
	  long long  s = 1;//输出结果
	scanf_s("%lld%lld%lld", &m, &n, &c);//计算m的n次方模c
	 
	while (n)
	{
		if (n & 1){ 
			s = s*m%c;
			n--;
		}//n为奇数
		n >>= 1;
		m = m*m%c;
	}
	 
	printf("%lld", s);
	return 0;
}