快速幂（取模）算法

问题

计算取模运算的值 $ a^n % b$，其中a、b、n均为int类型的变量。

分析

因为 $a^n$ 可能很大，所以不能先计算 $a^n$ 再将其 $ %b$ 。

现有取模公式，写作：

$ (a*b) % c = [ (a % c) \times (b % c) ] % c $

那么：

• 幂为偶数，则有 $ a^n % b = (a^{\frac n 2} \times a^{\frac n 2}) % b = [(a^{\frac n 2} % b) \times (a^{\frac n 2}) % b ] % b​$
• 幂为奇数，则有 $ (a \times a^{n-1}) % b = [(a % b) \times (a^{n-1} % b)] %b $，其中 $ a^{n-1} % b$ 对应到幂为偶数的情况

代码

递归

递归写法（会溢出）

int fastPower(int a, int b, int n) {
    if (n == 0) {
        return 1 % b;
    } else if (n == 1) {
        return a % b;
    }

    if (n % 2 == 1) {
        return ((a % b) * fastPower(a, b, n - 1)) % b;
    } else {
        int res = fastPower(a, b, n / 2);
        return (res * res) % b;
    }
}

溢出点：

• 奇数幂时，在计算 res * res 时可能超出int范围。
• 偶数幂时，在计算(a % b) * fastPower(a, b, n - 1) 时可能超出范围

改正后：

int fastPower(int a, int b, int n) {
    if (n == 0) {
        return 1 % b;
    } else if (n == 1) {
        return a % b;
    }
    
    if (n % 2 == 1) {
        return ((a % b) * (long long)fastPower(a, b, n - 1)) % b;
    } else {
        long long res = fastPower(a, b, n / 2) % b;
        return (res * res) % b;
    }
}

迭代

所有的递归函数都能写成迭代的形式。

int fastPower(int a, int b, int n) {
    long long r = 1, aa=a;
    while(n) {
        if (n & 1 == 1) r = (r * aa) % b;
        n >>= 1;
        aa = (aa * aa) % b;
    }
    return r % b;
}