葫芦娃关于快速幂流程的详细讲解

快速幂的流程大概是这样的，维护一个等式a^b=x^y*z。

比如说现在求3的10次方

第一步：3^10=3^10*1

第二步:3^10*1=9^5*1

第三步：9^5*1=9^4*9

第四步：9^4*9=81^2*9

第五步：81^2*9=6561^1*9

第六步：6561^1*9=1^1*59049

所以3^10=59049

上面总共进行了五次乘法运算，相比较朴素的十次来说，要好一些

经过上面的演算，抽象成自然语言大概是这样：

初始化，x=a,y=b,z=1，

每一次，首先如果y不大于0则退出，

然后判断y，若为奇数，那么z=z*x，

最后，y=y/2。

退出之后答案就是z了。

附上我的实现代码：

int work(int a,int b)
{
	int x=a,y=b,z=1;
	while(y>0)
	{
		if(y&1)
			z*=x;
		x*=x;
		y>>=1;
	}
	return z;
}

葫芦娃关于快速幂流程的详细讲解

原文：http://blog.csdn.net/stl112514/article/details/43853393