快速幂

Fast Power

TypeScript 
export function fastPow(a: number, n: number): number {
    const $ = BigInt
    const MOD = $(1e9 + 7)
    let b = $(a) % MOD
    let res = 1n
    while (n) {
        if (n % 2 === 1) res = (res * b) % MOD

        b = (b * b) % MOD
        n = Math.trunc(n / 2)
    }
    return Number(res % MOD)
}
JavaScript 
export function fastPow(a, n) {
    const $ = BigInt
    const MOD = $(1e9 + 7)
    let b = $(a) % MOD
    let res = 1n
    while (n) {
        if (n % 2 === 1) res = (res * b) % MOD
        b = (b * b) % MOD
        n = Math.trunc(n / 2)
    }
    return Number(res % MOD)
}
Rust 
pub fn fast_pow(a: i64, mut n: i64, m: i64) -> i64 {
    let mut b = a % m;
    let mut res = 1;
    while n > 0 {
        if n & 1 == 1 {
            res = (res * b) % m;
        }
        b = (b * b) % m;
        n = n / 2;
    }
    return res % m;
}
Java 

class Fastpow {

    public static long fastpow(long a, long b, long MOD) {
        long base = a % MOD, res = 1;
        while (b != 0) {
            if ((b & 1) == 1) {
                res = res * base % MOD;
            }
            base = base * base % MOD;
            b >>>= 1;
        }
        return res % MOD;
    }

    public static long fastpow(long a, long b) {
        int MOD = (int) 1e9 + 7;
        return fastpow(a, b, MOD);
    }
}
Python 
# python 的 built-in pow 自带快速幂
# pow(base, exp, mod)
Go 
package algo

func FastPow(a, n, m int64) int64 {
    b := a % m
    res := int64(1)
    for n > 0 {
        if n&1 == 1 {
            res = (res * b) % m
        }
        b = b * b % m
        n = n / 2
    }
    return res % m
}