Python：计算一个巨大的斐波那契数模 m

Question

# Uses python3
# Given two integers n and m, output Fn mod m (that is, the remainder of Fn when divided by m
def Huge_Fib(n,m):

    if n == 0 : return 0
    elif n == 1: return 1
    else:
        a,b = 0,1
        for i in range(1,n):
            a, b = b, (a+b) % m
        print(b);

n,m = map(int, input().split());   
Huge_Fib(n,m);

代码运行良好。但是，当我运行一个case为n=99999999999999999，m=2的时候，我花了很多时间。你有更好的解决方案吗？

Answer 1

你应该查查皮萨诺时期。 https://en.wikipedia.org/wiki/Pisano_period 和 http://webspace.ship.edu/msrenault/fibonacci/fibfactory.htm 应该能让你很好地理解它们是什么。

编辑：谷歌搜索 "fibonacci modulo" 给你这两个作为前两个结果。

Answer 2

# Uses python3
# Given two integers n and m, output Fn mod m (that is, the remainder of Fn when divided by m
def Huge_Fib(n,m):

    # Initialize a matrix [[1,1],[1,0]]    
    v1, v2, v3 = 1, 1, 0  
    # Perform fast exponentiation of the matrix (quickly raise it to the nth power)
    for rec in bin(n)[3:]:
        calc = (v2*v2) % m
        v1, v2, v3 = (v1*v1+calc) % m, ((v1+v3)*v2) % m, (calc+v3*v3) % m
        if rec == '1': v1, v2, v3 = (v1+v2) % m, v1, v2
    print(v2);        

n,m = map(int, input().split());   
Huge_Fib(n,m);

这是一个超快的解决方案，参考

Answer 3

这是我的解决方案，如果找到皮萨诺周期，则不必经过 99999999999999999 次迭代。

我还推荐你看这个视频：https://www.youtube.com/watch?v=Nu-lW-Ifyec

# Uses python3
import sys

def get_fibonacci_huge(n, m):
    if n <= 1:
        return n

    arr = [0, 1]
    previousMod = 0
    currentMod = 1

    for i in range(n - 1):
        tempMod = previousMod
        previousMod = currentMod % m
        currentMod = (tempMod + currentMod) % m
        arr.append(currentMod)
        if currentMod == 1 and previousMod == 0:
            index = (n % (i + 1))
            return arr[index]

    return currentMod

if __name__ == '__main__':
    input = sys.stdin.read();
    n, m = map(int, input.split())
    print(get_fibonacci_huge(n,m))

Answer 4

在下面的代码中，我们使用了斐波那契数列的两个概念：

皮萨诺周期遵循斐波那契数列，因此每个重复（模式）都以 0 和 1 开始，一个接一个地连续出现。
fib(n) 仅当 n 除以 m 时才除以 fib(m) 即如果 fib(4)%3==0,则 fib(4+4)%3==0, fib(4+4+4)%3==0 等 on.This 帮助我们找到皮萨诺周期。

想了解皮萨诺时期，推荐你看这个视频：https://www.youtube.com/watch?v=Nu-lW-Ifyec

#python3
def pisano_length(m):
    i=2
    while(fib(i)%m!=0):
        i+=1
    if(fib(i+1)%m!=1):
        while(fib(i+1)%m!=1):
            i+=i
    print("The pisano length for mod {} is: {}".format(m,i))
    return(i)
def fib(n):
    a,b=0,1
    if(n==0 or n==1):
        return n
    else:
        for i in range(2,n+1):
            b,a=a+b,b
    return(b)
#we want to calculate fib(n)%m for big numbers
n,m=map(int,input().split())
remainder=n%pisano_length(m)
print(fib(remainder)%m)

Answer 5

对于任何整数 m>=2，序列 fn 模 m 是周期性的 - 皮萨诺周期。所以不需要存储和查找fn。相反，找到给定 m 的重复模式。

Answer 6

这就是我计算皮萨诺周期的方法。(Java)

public static long get_pisano_period(long m) {
    long a = 0, b = 1;
    long c;
    for (int i = 0; i < m * m; i++) {
        c = (a + b) % m;
        a = b;
        b = c;
        if (a == 0 && b == 1)
            return i + 1;
    }
    return 0;
}

public static BigInteger get_fibonacci_huge(long n,long m) {
    long remainder = n % get_pisano_period(m);

    BigInteger first = BigInteger.valueOf(0);
    BigInteger second=BigInteger.valueOf(1);
    BigInteger m1=BigInteger.valueOf(m);
    BigInteger res = BigInteger.valueOf(remainder);

    for (long i = 1; i < remainder; i++) {
        res = (first.add(second)).mod(m1);
        first = second;
        second = res;
    }
    return res.mod(m1);
}

Answer 7

我在 Python 中解决了它 3. 这是计算一个巨大的斐波那契数模的最快算法 m.For 例如 n =2816213588，m = 239，它花费了最大使用时间：0.01/ 5.00，使用的最大内存：9424896/536870912。）

     def pisanoPeriod(m): 
        previous, current = 0, 1
        for i in range(0, m * m): 
            previous, current = current, (previous + current) % m 
            # A Pisano Period starts with 01 
            if (previous == 0 and current == 1): 
                return i + 1

    def calc_fib(n,m):
        p = pisanoPeriod(m)
        n = n % p
        if (n <= 1):
            return n
        else:
          previous,current = 0,1
          for i in range(2,n+1):
            previous,current = current,(previous+current)
        return current%m

    n,m =map(int,input().split(" "))
    print(calc_fib(n,m))

Python：计算一个巨大的斐波那契数模 m

Python: Compute a Huge Fibonacci Number Modulo m

python-3.x

fibonacci

modulo