快速幂 快速幂取模
快速幂 求 x^m 一般方法是 xm = x * xm-1，这样需要做 m 次乘法，未免过慢。 加速方法有两种。 1.基于当 m 为偶数时， xm = (x2)^(m/2) ；当 m 为奇数时， xm = x * xm-1。显然当 m 为偶数时 m 会减半，当 m 为奇数时，下次就是偶数。m 可以很快收敛到 0.（^表示幂） 2.将 m 看成二进制串 mkmk-1…m1m0，那么 xm = xm02^0 + m12^1 + … + mk2^k = xm02^0 * xm1*2^1 _ … _ xmk*2^k. mi 为 0 或 1，假设平均有一半 mi 为 1，即 k 个，那么总共才只需要做（k+(k/2)）次乘法。 下面给出代码。第一个方法是加速方法 1，第二个方法是加速方法 1 的迭代形式，第三个方法是加速方法 2。 ...