次方的快速算法？

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;}