蓝桥杯2014年第五届真题-斐波那契（Python题解）

解题思路:

注意事项:

参考代码:

while True:

    try:

        n,m,p = map(int,input().split())

        M = [[1,1],[1,0]]

        def mulMatrix(x, y,mod):  # 定义二阶矩阵相乘的函数

            ans = [[0 for i in range(2)] for j in range(2)]

            for i in range(2):

                for j in range(2):

                    for k in range(2):

                        ans[i][j] += (x[i][k] * y[k][j])%mod

            return ans

        def quickMatrix(M, N,mod):      #矩阵快速幂

            E = [[1,0],[0,1]]  # 先定义一个单位矩阵

            while (N):

                if N % 2 != 0:

                    E = mulMatrix(E,M,mod)

                M = mulMatrix(M,M,mod)

                N >>= 1

            return E

        def fib(M,q,mod):     #返回第q个斐波那契数

            s = [[1,1],[0,0]]

            res = mulMatrix(s,quickMatrix(M,q-2,mod),mod)[0][0]%mod

            return res

        def mulMatrix_1(x, y):  # 定义二阶矩阵相乘的函数

            ans = [[0 for i in range(2)] for j in range(2)]

            for i in range(2):

                for j in range(2):

                    for k in range(2):

                        ans[i][j] += x[i][k] * y[k][j]

            return ans

        def quickMatrix_1(M, N):      #矩阵快速幂

            E = [[1,0],[0,1]]  # 先定义一个单位矩阵

            while (N):

                if N % 2 != 0:

                    E = mulMatrix_1(E,M)

                M = mulMatrix_1(M,M)

                N >>= 1

            return E

        def fib_1(M,q):     #返回第q个斐波那契数

            s = [[1,1],[0,0]]

            res = mulMatrix_1(s,quickMatrix_1(M,q-2))[0][0]

            return res

        if m >= n+2:

            print(fib(M,n+2,p)%p-1)

        else:

            mod = fib_1(M,m)

            print(fib(M,n+2,mod)%fib_1(M,m)%p-1)

    except:

        break