描述

計(jì)算 a^n % b，其中 a，b 和 n 都是 32 位的整數(shù)。

樣例

例如 2^31 % 3 = 2
例如 100^1000 % 1000 = 0

挑戰(zhàn)

O(logn)

思路

a ^ 2n = (a ^ n) * (a ^ n)
a ^ 2n + 1 = (a ^ n) * (a ^ n) * a
把冪次方拆成一半乘一半

代碼

class Solution {
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        if (n == 1) {
            return a % b;
        }
        if (n == 0) {
            return 1 % b;
        }
        
        // 用 long 類型不會(huì)有精度損失，結(jié)果準(zhǔn)確
        long product = fastPower(a, b, n >> 1);
        product = (product * product) % b;
        if ((n & 0x1) == 1) {
            product = (product * a) % b;
        }
        return (int) product;
    }
}

注意

1. 位運(yùn)算的左移替代除 2 和與運(yùn)算替代取余更有效率
2. 答案是最終版本的優(yōu)化算法，笨方法是用 for 循環(huán)從 1 循環(huán)到 n，比較沒(méi)效率，但無(wú)論哪種做法都需要考慮底數(shù)為 0 并且冪次方為負(fù)的特殊情形。

下面是劍指offer書上的原話

代碼

描述