快速幂算法,幂运算算法

运行时间由线性O(N)到对数O(logN)
如果幂为偶数，XN=XN/2 *XN/2,
如果幂为奇数，XN=X（N-1）/2 *X（N-1）/2 *X,

如：X62求解只用9次乘法
X3=X2*X，
X7=(X3)2*X,
…
X62=(X31 )2

static long myPow(long x, int n) { if (n == 0) { return 1; } if (n % 2 == 0) { return myPow(x * x, n / 2); } else { return myPow(x * x, n / 2) * x; } }

源自《数据结构与算法分析》，推荐阅读。