快速幂

快速的计算出 , 时间复杂度达到

思路：预计算出然后组合为

即把 k 拆解为多个以 2 为底的多个数的和。具体通过 2进制来拆解。

例如

所以最多拆解为个数字相乘。

那么如何快速预计算出呢？

通过这个依次计算出来log k 个预处理的值。即每一个数都是上一个数字的平方，且只需要平方k次

例：


def qmi(a, k):
    res = 1
    while k:
        # 如果当前二进制位 为 1
        if k & 1:
            res = res * a
        # 计算下一个 a 
        a = a * a
        k = k >> 1

    return res


# 递归版本
def qmi(a, k):
    if k == 0:
        return 1
    elif k % 2 == 0:
        temp = qmi(a, k//2)
        return temp * temp
    else:
        return qmi(a, k-1) * a

矩阵的快速幂


def matrix_matual(A, B):
		pass