Fibonacci módulo p

La sucesión de Fibonacci se define como  =  +  donde  = 1 y  = 1 son las semillas. 
Para un número primo p dado, considere una nueva secuencia que es (secuencia de Fibonacci) mod p. Por ejemplo para p = 5, la nueva sucesión sería 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4… El cero mínimo de la nueva sucesión se define como el primer número de 
Fibonacci que es un múltiplo de p o  mod p = 0. 
Dado primo no p, encuentre el cero mínimo de la secuencia de Fibonacci módulo p.
Ejemplos: 
 

Input : 5
Output : 5
The fifth Fibonacci no (1 1 2 3 5) 
is divisible by 5 so 5 % 5 = 0.

Input : 7
Output : 8
The 8th Fibonacci no (1 1 2 3 5 8 13 21) 
is divisible by 7 so 21 % 7 = 0.

Un enfoque simple es seguir calculando números de Fibonacci y para cada uno de ellos calcular Fi mod p. Sin embargo, si observamos esta nueva sucesión, denotemos  el  término de la sucesión, entonces sigue:  = ( +  ) mod pie el resto  es en realidad la suma de los restos de los dos términos anteriores de esta serie. Por lo tanto, en lugar de generar la sucesión de Fibonacci y luego tomar el módulo de cada término, simplemente sumamos los dos restos anteriores y luego tomamos su módulo p. 
A continuación se muestra la implementación para encontrar el 0 mínimo. 
 

// C++ program to find minimal 0 Fibonacci
// for a prime number p
#include<bits/stdc++.h>
using namespace std;
 
// Returns position of first Fibonacci number
// whose modulo p is 0.
int findMinZero(int p)
{
    int first = 1, second = 1, number = 2, next = 1;
    while (next)
    {
        next = (first + second) % p;
        first = second;
        second = next;
        number++;
    }
    return number;
}
 
// Driver code
int main()
{
    int p = 7;
    cout << "Minimal zero is: "
        << findMinZero(p) << endl;
    return 0;
}

// Java program to find minimal 0 Fibonacci
// for a prime number p
import java.io.*;
 
class FibZero
{
    // Function that returns position of first Fibonacci number
    // whose modulo p is 0
    static int findMinZero(int p)
    {
        int first = 1, second = 1, number = 2, next = 1;
        while (next > 0)
        {
            // add previous two remainders and
            // then take its modulo p.
            next = (first + second) % p;
            first = second;
            second = next;
            number++;
        }
        return number;
    }
     
    // Driver program
    public static void main (String[] args)
    {
        int p = 7;
        System.out.println("Minimal zero is " + findMinZero(p));
    }
}

# Python 3 program to find minimal
# 0 Fibonacci for a prime number p
 
# Returns position of first Fibonacci
# number whose modulo p is 0.
def findMinZero(p):
    first = 1
    second = 1
    number = 2
    next = 1
 
    while (next):
        next = (first + second) % p
        first = second
        second = next
        number = number + 1
     
    return number
 
# Driver code
if __name__ == '__main__':
    p = 7
    print("Minimal zero is:", findMinZero(p))
 
# This code is contributed by
# Surendra_Gangwar

// C# program to find minimal 0
// Fibonacci for a prime number p
using System;
 
class GFG {
     
    // Function that returns position
    // of first Fibonacci number
    // whose modulo p is 0
    static int findMinZero(int p)
    {
        int first = 1, second = 1;
        int number = 2, next = 1;
        while (next > 0)
        {
             
            // add previous two
            // remainders and then
            // take its modulo p.
            next = (first + second) % p;
            first = second;
            second = next;
            number++;
        }
        return number;
    }
     
    // Driver program
    public static void Main ()
    {
        int p = 7;
        Console.WriteLine("Minimal zero "
              + "is :" + findMinZero(p));
    }
}
 
// This code is contributed by anuj_67.

<?php
// PHP program to find
// minimal 0 Fibonacci
// for a prime number p
 
// Returns position of
// first Fibonacci number
// whose modulo p is 0.
function findMinZero($p)
{
    $first = 1;
    $second = 1;
    $number = 2;
    $next = 1;
    while ($next)
    {
        $next = ($first +
                 $second) % $p;
        $first = $second;
        $second = $next;
        $number++;
    }
 
    return $number;
}
 
// Driver code
$p = 7;
echo "Minimal zero is: ",
    findMinZero($p), "\n";
 
// This code is contributed
// by akt_mit
?>

<script>
// Javascript program to find
// minimal 0 Fibonacci
// for a prime number p
 
// Returns position of
// first Fibonacci number
// whose modulo p is 0.
function findMinZero(p)
{
    let first = 1;
    let second = 1;
    let number = 2;
    let next = 1;
    while (next)
    {
        next = (first +
                second) % p;
        first = second;
        second = next;
        number++;
    }
 
    return number;
}
 
// Driver code
let p = 7;
document.write("Minimal zero is: ",
    findMinZero(p) + "<br>");
 
// This code is contributed
// by akt_mit
</script>

Producción: 
 

Minimal zero is: 8

Este artículo es una contribución de Aditi Sharma . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.