【算法日记】快速幂：关于我知道答案却做不出来这档事

// 直接将x连乘n次即可
// 时间复杂度 O(n)
function myPow(x: number, n: number): number {
    let m: number = 1
    // 遇到负数需要连乘 1/x
    if(n<0) x = 1/x
    for(let i=0;i<Math.abs(n);i++) {
        m*=x
    }
    return m
}

// 对 n 进行折半计算，无需重复连乘
// 时间复杂度 O(logn)
function myPow(x: number, n: number): number {
    function myPowHandler(x: number, n: number): number{
        // n 等于 1 返回本身即可
        if(n===1) return x

        // n为奇数需要计算 x**((n-1)/2) * x**((n-1)/2) * x**1
        if(n%2!==0) {
            const half = myPowHandler(x, Math.floor(n/2))
            return half * half * x
        }
        // n为偶数需要计算 x**(n/2) * x**(n/2)
        else {
            const half = myPowHandler(x, Math.floor(n/2))
            return half * half
        }
    }
    // 特殊条件
    // x为1 或 n为0 即返回 1
    if(x===1 || n===0) return 1
    // 负数情况返回 1/x**n
    if(n<0) return 1 / myPowHandler(x, Math.abs(n))
    return myPowHandler(x, n)
};

function myPow(x, n) {
    // 特殊情况判断
    if(n===0) return 1
    else if(n===1) return x
    // 负数计算为倒数的幂
    else if(n < 0) return myPow(1/x, Math.abs(n))
    // 判断奇偶
    // 如果为偶数计算 (x*x)**(n/2)
    // 如果为奇数计算 (x*x)**(n/2)*x
    // 递归结束条件为 n===0 || n===1 （即条件一）
    else return n%2===0 ? myPow(x*x, n/2) : myPow(x*x, Math.floor(n/2))*x
};

// 观察后发现我们可以知道答案是 x**n - 2
// 并且答案可能过大需要取余
// 由于精度问题 均需要使用BigInt 而不是Number

function monkeyMove(n: number): number {
    const MOD = BigInt(1e9 + 7)
    // 直接把快速幂搬过来加上取余即可
    function myPow(x: bigint, n: bigint) {
        if(n===0n) return 1
        else if(n===1n) return x
        else return n%2n===0n ? myPow(x*x%MOD, n/2n) : myPow(x*x%MOD, n/2n)*x
    };
    // +MOD是因为-2后结果可能为负数
    return Number((myPow(2n, BigInt(n)) - 2n + MOD) % MOD)
};