python-矩阵乘方

解题思路:

递归。

注意事项:

注意当b = 0时，A = I % m，不要直接写成A = [[1,0],[0,1]]，因为当m = 1时，此时，A = I%m = [[0,0],[0,0]]。

参考代码:

def mul(flag):  
    global m  
    global A  
    global AA  
  
    temp = [[0,0],[0,0]]  
    if flag == 1:  
        B = A[:]  
    elif flag == 2:  
        B = AA[:]  
  
    for i in range(2):  
        for j in range(2):  
            for k in range(2):  
                temp[i][j] = temp[i][j] + A[i][k]*B[k][j]      
    
    for i in range(2):  
        for j in range(2):  
            A[i][j] = temp[i][j] % m  
  
def f(b):  
    global m  
    global A  
  
    if b == 0:  
        A[0] = [1%m,0]  
        A[1] = [0,1%m]  
        return   
  
    if b % 2 == 0:  
        b = b // 2  
        f(b)                          #注意f()和mul()不要写反了。先递归调用的最后一层，然后依次往外乘。  
        mul(1)  
        return  
  
    if b % 2 == 1:  
        b = b - 1  
        f(b)  
        mul(2)  
        return  
  
  
if __name__ == '__main__':  
    b,m = map(int,input().split())  
    A = [[int(i) for i in input().split()]]  
    A = A + [[int(i) for i in input().split()]]  
    AA = A[:]  
  
    f(b)  
    for i in range(2):  
        for j in range(2):  
            print(A[i][j],end=' ')  
        print()