algorithm - 在 Python 中计算一个巨大的斐波那契数模 m

Question

这个问题的目标是计算F[n] mod m。这里的输入是n和m，其中n代表斐波那契数的索引，比如F[0] = 0, F[ 1] = 1，F[2] = 1，F[3]= 2，m 代表 F[n] 将除以的数。约束是:

• n >= 1 且 n <= 10^18
• m >= 2 且 m <= 10^5

到目前为止我已经解决了这个问题并且能够生成这个问题的确切输出，除非我给 100000 作为 m 的值，它超过了时间限制。时间限制为 5 秒。如果 m 的值在 2 到 99999 之间(包括 2 到 99999)，我的程序会在时限内生成正确的输出。任何形式的帮助解决这个问题将不胜感激。

代码:

def fibonacci(n):
    if ( n == 0 ):
        return (0, 1)
    else:
        a, b = fibonacci(n/2)
        c = a * (2* b - a)
        d = a**2 + b**2
        if ( n % 2 ):
            return (d, c + d)
        else:
            return (c, d)


def findRemainders(m):
    remainderList = ["0", "1"]
    i = 2
    while(1):
        firstFib, secondFib = fibonacci(i)
        if ( (firstFib % m) == 0 and (secondFib % m) == 1 ):
            break
        remainderList.append( (firstFib % m) )
        remainderList.append( (secondFib % m) )
        i += 2

    return remainderList


def hugeFibonacciNumberModulo_m( n, m ):
    remainderList = findRemainders(m)
    length_of_period = len(remainderList)
    remainder = (n % length_of_period)
    out = remainderList[remainder]
    return out


inp = map(int, raw_input().split())
n, m = inp[0], inp[1]

if ( (n >= 1 and n <= 10**18) and (m >= 2 and m <= 10**5) ):
    out = hugeFibonacciNumberModulo_m( n, m )
print out

Answer 1

您可以使用模幂运算非常快速地完成此操作。

考虑以下矩阵乘法:

| 0  1 |     | a |     |  b  |
|      |  x  |   |  =  |     |
| 1  1 |     | b |     | a+b |

如果 a 和 b 是最后两项，您应该立即看到乘法的结果是斐波那契数列的下一次迭代。要获得执行此乘法 n 次的结果，您需要计算 2x2 矩阵 (0,1;1,1) 的 n 次 次幂 (mod m)。这可以通过将该矩阵提高到 2 的连续幂来非常快速地完成。

例如，要计算此矩阵的 10 次方:

                   | 0  1 |     | 0  1 |     | 1  1 |
A x A  =  A**2  =  |      |  x  |      |  =  |      |
                   | 1  1 |     | 1  1 |     | 1  2 |

                      | 1  1 |     | 1  1 |     | 2  3 |
A**4 =  (A**2)**2  =  |      |  x  |      |  =  |      |
                      | 1  2 |     | 1  2 |     | 3  5 |

                      | 2  3 |     | 2  3 |     | 13  21 |
A**8 =  (A**4)**2  =  |      |  x  |      |  =  |        |
                      | 3  5 |     | 3  5 |     | 21  34 |

对矩阵进行三次平方后，我们现在有了 A**8 和 A**2 的值。将它们相乘得到 A**10:

          | 13  21 |     | 1  1 |     | 34  55 |
A**10  =  |        |  x  |      |  =  |        |
          | 21  34 |     | 1  2 |     | 55  89 |

这些数字在常规算术中会迅速变得巨大，但如果您执行所有乘法模 m，那么这不是问题。最后，将向量 (0; 1) 乘以结果矩阵得到答案(或者，等价地，只选择矩阵顶行的第二个数字)。

所需的乘法次数为log(n) 量级，因此所需时间应该非常小，即使m 为一万亿或更多。

See Wikipedia for more information about modular exponentiation of matrices.