在Python中以模为模计算巨大的斐波那契数 [英] Calculating a huge fibonacci number modulo m in Python

问题描述

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

The goal of this problem is to calculate F[n] mod m. Here the inputs are n and m, where n stands for the index of the fibonacci number, say F[0] = 0, F[1] = 1, F[2] = 1, F[3]= 2 and m stands for the number by which F[n] will be divided. The constraints are:

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

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

I have gone this problem so far and been able to generate the exact output of this problem except when I give 100000 as the value of m, it exceeds the time limit. The time limit is 5 seconds. If the value of m is given between and including from 2 to 99999, my program generates the correct output within the time limit. Any kind of help solving this problem would be highly appreciated.

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

推荐答案

我不明白您要在 findRemainders(m)中尝试做什么或为什么需要它.您已经在使用斐波那契加倍算法，该算法类似于(并且通常派生自)矩阵乘方平方算法.可以通过在每个步骤上基本修改部分结果来修改幂运算以有效地处理模幂.

I don't understand what you're attempting to do in findRemainders(m) or why you need it. You're already using the Fibonacci-by-doubling algorithm, which is analogous to (and usually derived from) a matrix-exponentiation-by-squaring algorithm. Exponentiation can be modified to efficiently handle modular exponentiation by essentially mod'ing your partial result(s) at each step.

def fibmod(n, m):
    assert 1 <= n <= 10**18, n
    assert 2 <= m <= 10**5, m

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

            if n % 2 == 0:
                return c, d
            else:
                return d, (c + d) % m

    return f(n)[0]

您可以进一步分解 c 和 d 的表达式，并在每个中间乘法，加法和减法之后将％m 应用于防止溢出(但这在Python中并不是真正的问题).

You can break down the expression for c and d even further and apply % m after each intermediate multiplication, addition, and subtraction to prevent overflow (but this isn't really a problem in Python).

这篇关于在Python中以模为模计算巨大的斐波那契数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！