Número de Fibonacci módulo M y período de Pisano

Posted on by Rudeus Greyrat

Dados dos números N y M . La tarea es encontrar el N-ésimo número de Fibonacci mod M.
En general, sea F N el N-ésimo número de fibonacci, entonces la salida debería ser F N % M .

La sucesión de Fibonacci es una serie de números en los que cada núm. es la suma de los dos números precedentes. Se define por la relación de recurrencia: 

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2

Estos núms. están en la siguiente secuencia: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
Aquí N puede ser grande.

Ejemplos: 

Entrada: N = 438, M = 900 
Salida: 44

Entrada: N = 1548276540, M = 235 
Salida: 185  

Enfoque: 
Sin embargo, para tales valores de N , debe evitarse un enfoque recursivo simple para seguir calculando N números de Fibonacci con una complejidad temporal de O(2 N ) . Incluso un enfoque iterativo o de programación dinámica con un algoritmo en bucle para N iteraciones no será eficiente en el tiempo.
Este problema se puede resolver utilizando las propiedades del Período Pisano . 
Para un valor dado de N y M >= 2, la serie generada con F i módulo M (para i en el rango (N)) es periódica. 

El período siempre comienza con 01. El Período Pisano se define como la duración del período de esta serie.
Para entenderlo mejor, veamos qué sucede cuando M es pequeño:

i 0 1 2 3 4 5 6 7 8 9 10 11
yo _ 0 1 1 2 3 5 8 13 21 34 55 89
F yo mod 2 0 1 1 0 1 1 0 1 1 0 1 1
F mod 3 0 1 1 2 0 2 2 1 0 1 1 2

Para M = 2, el período es 011 y tiene una longitud de 3 mientras que para M = 3 la secuencia se repite después de 8 números.

Ejemplo: 
Entonces, para calcular, digamos F 2019 mod 5, encontraremos el resto de 2019 cuando se divide por 20 (el período Pisano de 5 es 20). 2019 mod 20 es 19. Por lo tanto, F 2019 mod 5 = F 19 mod 5 = 1. Esta propiedad es cierta en general. 
Necesitamos encontrar el resto cuando N se divide por el Período Pisano de M . Luego calcule F (N) resto mod M para el N recién calculado .

A continuación se muestra la implementación de F N módulo M:

C++

// C++ program to calculate
// Fibonacci no. modulo m using
// Pisano Period
#include <bits/stdc++.h>
using namespace std;
 
// Calculate and return Pisano Period
// The length of a Pisano Period for
// a given m ranges from 3 to m * m
long pisano(long m)
{
    long prev = 0;
    long curr = 1;
    long res = 0;
 
    for(int i = 0; i < m * m; i++)
    {
        long temp = 0;
        temp = curr;
        curr = (prev + curr) % m;
        prev = temp;
 
        if (prev == 0 && curr == 1)
            res = i + 1;
    }
    return res;
}
 
// Calculate Fn mod m
long fibonacciModulo(long n, long m)
{
     
    // Getting the period
    long pisanoPeriod = pisano(m);
 
    n = n % pisanoPeriod;
 
    long prev = 0;
    long curr = 1;
 
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
 
    for(int i = 0; i < n - 1; i++)
    {
        long temp = 0;
        temp = curr;
        curr = (prev + curr) % m;
        prev = temp;
    }
    return curr % m;
}
 
// Driver Code
int main()
{
    long n = 1548276540;
    long m = 235;
 
    cout << (fibonacciModulo(n, m));
    return 0;
}
 
// This code is contributed by subhammahato348

Java

// Java program to calculate
// Fibonacci no. modulo m using
// Pisano Period
import java.io.*;
 
class GFG{
     
// Calculate and return Pisano Period
// The length of a Pisano Period for
// a given m ranges from 3 to m * m
public static long pisano(long m)
{
    long prev = 0;
    long curr = 1;
    long res = 0;
     
    for(int i = 0; i < m * m; i++)
    {
        long temp = 0;
        temp = curr;
        curr = (prev + curr) % m;
        prev = temp;
         
        if (prev == 0 && curr == 1)
            res= i + 1;
    }
    return res;
}
 
// Calculate Fn mod m
public static long fibonacciModulo(long n,
                                   long m)
{
     
    // Getting the period
    long pisanoPeriod = pisano(m);
     
    n = n % pisanoPeriod;
     
    long prev = 0;
    long curr = 1;
     
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
     
    for(int i = 0; i < n - 1; i++)
    {
        long temp = 0;
        temp = curr;
        curr = (prev + curr) % m;
        prev = temp;
    }
    return curr % m;
}
 
// Driver Code
public static void main(String[] args)
{
    long n = 1548276540;
    long m = 235;
     
    System.out.println(fibonacciModulo(n, m));
}
}
 
// This code is contributor by Parag Pallav Singh

Python3

# Python3 program to calculate
# Fibonacci no. modulo m using
# Pisano Period
 
# Calculate and return Pisano Period
# The length of a Pisano Period for
# a given m ranges from 3 to m * m
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
 
# Calculate Fn mod m
def fibonacciModulo(n, m):
     
    # Getting the period
    pisano_period = pisanoPeriod(m)
     
    # Taking mod of N with
    # period length
    n = n % pisano_period
     
    previous, current = 0, 1
    if n==0:
        return 0
    elif n==1:
        return 1
    for i in range(n-1):
        previous, current \
        = current, previous + current
         
    return (current % m)
 
# Driver Code
if __name__ == '__main__':
    n = 1548276540
    m = 235
    print(fibonacciModulo(n, m))

C#

// C# program to calculate
// Fibonacci no. modulo m using
// Pisano Period
using System;
 
class GFG {
 
    // Calculate and return Pisano Period
    // The length of a Pisano Period for
    // a given m ranges from 3 to m * m
    public static long pisano(long m)
    {
        long prev = 0;
        long curr = 1;
        long res = 0;
 
        for (int i = 0; i < m * m; i++) {
            long temp = 0;
            temp = curr;
            curr = (prev + curr) % m;
            prev = temp;
 
            if (prev == 0 && curr == 1)
                res = i + 1;
        }
        return res;
    }
 
    // Calculate Fn mod m
    public static long fibonacciModulo(long n, long m)
    {
 
        // Getting the period
        long pisanoPeriod = pisano(m);
 
        n = n % pisanoPeriod;
 
        long prev = 0;
        long curr = 1;
 
        if (n == 0)
            return 0;
        else if (n == 1)
            return 1;
 
        for (int i = 0; i < n - 1; i++) {
            long temp = 0;
            temp = curr;
            curr = (prev + curr) % m;
            prev = temp;
        }
        return curr % m;
    }
 
    // Driver Code
    public static void Main()
    {
        long n = 1548276540;
        long m = 235;
 
        Console.Write(fibonacciModulo(n, m));
    }
}
 
// This code is contributed by subham348.

Javascript

<script>
 
// javascript program to calculate
// Fibonacci no. modulo m using
// Pisano Period
// Calculate and return Pisano Period
// The length of a Pisano Period for
// a given m ranges from 3 to m * m
function pisano(m)
{
    let prev = 0;
    let curr = 1;
    let res = 0;
 
    for(let i = 0; i < m * m; i++)
    {
        let temp = 0;
        temp = curr;
        curr = (prev + curr) % m;
        prev = temp;
 
        if (prev == 0 && curr == 1)
            res = i + 1;
    }
    return res;
}
 
// Calculate Fn mod m
function fibonacciModulo(n,m)
{
     
    // Getting the period
    let pisanoPeriod = pisano(m);
 
    n = n % pisanoPeriod;
 
    let prev = 0;
    let curr = 1;
 
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
 
    for(let i = 0; i < n - 1; i++)
    {
        let temp = 0;
        temp = curr;
        curr = (prev + curr) % m;
        prev = temp;
    }
    return curr % m;
}
 
 
    let n = 1548276540;
    let m = 235;
 
    document.write(fibonacciModulo(n, m));
     
    // This code is contributed by vaibhavrabadiya117.
</script>
Producción: 

185

 

El Período de Pisano de 235 es 160. 1548276540 mod 160 es 60. F 60 mod 235 = 185. Usando el Período de Pisano, ahora necesitamos calcular los números de Fibonacci. iterativamente para un N relativamente más bajo que el especificado en el problema original y luego calcule F N módulo M .
Complejidad del Tiempo: O(M 2 )

Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por ht_rohit y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *