次方的快速算法？

Question

次方的快速算法？

Answer 1

整数次方可以用快速幂算法
譬如计算x^y,可以先算出x^(y/2)
然后再自乘一次，如果y是奇数，那就再额外乘一次y
对于x^(y/2)，我们仍用上述方法递归计算，可以得到logy复杂度的算法
以下是循环写法，效率比递归写法略高一些
int pow(int x,int y)
{
int ans=1;
while(y)
{
if(y)ans*=x;
x*=x;
y>>=1;
}
return ans;
}