如何计算快速幂,比如 x^100000000次方,直接循环很慢.
问题描述:
如何计算快速幂,比如 x^100000000次方,直接循环很慢.
答
因为 x^n = (x^(n/2))^2根据这个公式,可以在 log2N时间内算出乘法幂递归算法:int pow(int x,int n){if(n==1) return x;else if(n&1) //n is odd{return x*pow(x,n/2);}else {return pow(x,n/2);}}非递归算法:int po...