Último dígito de la suma de números en el rango dado en la serie de Fibonacci

Dados dos enteros no negativos M, N que significa el rango [M, N] donde M ≤ N, la tarea es encontrar el último dígito de la suma de F _M + F _M+1 … + F _N donde F _K es el K ^-ésimo número de Fibonacci en la serie de Fibonacci . 
 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … 
 

Ejemplos: 
 

Entrada: M = 3, N = 9 
Salida: 6 
Explicación: 
Necesitamos encontrar F ₃ + F ₄ + F ₅ + F ₆ + F ₇ + F ₈ + F ₉ 
=> 2 + 3 + 5 + 8 + 13 + 21 + 34 = 86. 
Claramente, el último dígito de la suma es 6.
Entrada: M = 3, N = 7 
Salida: 1 
Explicación: 
Necesitamos encontrar F ₃ + F ₄ + F ₅ + F ₆ + F ₇ 
= > 2 + 3 + 5 + 8 + 13 = 31. 
Claramente, el último dígito de la suma es 1. 
 

Enfoque ingenuo: el enfoque ingenuo para este problema es encontrar uno por uno la suma de todos los K ^números de Fibonacci donde K se encuentra en el rango [M, N] y devolver el último dígito de la suma al final. La complejidad de tiempo para este enfoque es O(N) y este método falla para valores de orden superior de N. 
Enfoque eficiente: un enfoque eficiente para este problema es usar el concepto de Período Pisano . 
 

• La idea es calcular la suma de (M – 1) y N números de Fibonacci respectivamente, y restar el último dígito de los valores calculados.
• Esto se debe a que el último dígito de la suma de todos los K ^números de Fibonacci tales que K se encuentra en el rango [M, N] es igual a la diferencia de los últimos dígitos de la suma de todos los K números ^de Fibonacci en el rango [0, N] y la suma de todos los K ^-ésimos números de Fibonacci en el rango [0, M – 1] .
• Estos valores se pueden calcular respectivamente por el concepto del período de Pisano en un tiempo muy corto.
• Comprendamos cómo funciona el período pisano. La siguiente tabla ilustra los primeros 10 números de Fibonacci junto con sus valores obtenidos cuando se realiza el módulo 2 en los números.
   

•  
• Claramente, el período de Pisano para (F _i mod 2) es 3 ya que 011 se repite y longitud (011) = 3.
• Ahora, observemos la siguiente identidad: 
   

7 = 2 * 3 + 1 
Dividendo = (Cociente × Divisor) + Resto 
=> F ₇ mod 2 = F ₁ mod 2 = 1. 
 

• Por lo tanto, en lugar de calcular el último dígito de la suma de todos los números en el rango [0, N] , simplemente calculamos la suma hasta el resto dado que el período de Pisano para F _i mod 10 es 60.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to calculate
// last digit of the sum of the
// fibonacci numbers from M to N
#include<bits/stdc++.h>
using namespace std;
 
// Calculate the sum of the first
// N Fibonacci numbers using Pisano
// period
long long fib(long long n)
{
     
    // The first two Fibonacci numbers
    long long f0 = 0;
    long long f1 = 1;
 
    // Base case
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    else
    {
        // Pisano period for % 10 is 60
        long long rem = n % 60;
 
        // Checking the remainder
        if(rem == 0)
           return 0;
 
        // The loop will range from 2 to
        // two terms after the remainder
        for(long long i = 2; i < rem + 3; i++)
        {
           long long f = (f0 + f1) % 60;
           f0 = f1;
           f1 = f;
        }
         
        long long s = f1 - 1;
        return s;
    }
}
 
// Driver Code
int main()
{
    long long m = 10087887;
    long long n = 2983097899;
 
    long long final = abs(fib(n) - fib(m - 1));
    cout << final % 10 << endl;
}
 
// This code is contributed by Bhupendra_Singh

// Java program to calculate
// last digit of the sum of the
// fibonacci numbers from M to N
import java.util.*;
 
class GFG{
 
// Calculate the sum of the first
// N Fibonacci numbers using Pisano
// period
static int fib(long n)
{
     
    // The first two Fibonacci numbers
    int f0 = 0;
    int f1 = 1;
 
    // Base case
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    else
    {
         
        // Pisano period for % 10 is 60
        int rem = (int) (n % 60);
 
        // Checking the remainder
        if(rem == 0)
        return 0;
 
        // The loop will range from 2 to
        // two terms after the remainder
        for(int i = 2; i < rem + 3; i++)
        {
           int f = (f0 + f1) % 60;
           f0 = f1;
           f1 = f;
        }
         
        int s = f1 - 1;
        return s;
    }
}
 
// Driver Code
public static void main(String args[])
{
    int m = 10087887;
    long n = 2983097899L;
    int Final = (int)Math.abs(fib(n) -
                              fib(m - 1));
     
    System.out.println(Final % 10);
}
}
 
// This code is contributed by AbhiThakur

# Python3 program to calculate
# Last Digit of the sum of the
# Fibonacci numbers from M to N
 
# Calculate the sum of the first
# N Fibonacci numbers using Pisano
# period
def fib(n):
 
    # The first two Fibonacci numbers
    f0 = 0
    f1 = 1
 
    # Base case
    if (n == 0):
        return 0
    if (n == 1):
        return 1
    else:
 
        # Pisano Period for % 10 is 60
        rem = n % 60
 
        # Checking the remainder
        if(rem == 0):
            return 0
 
        # The loop will range from 2 to
        # two terms after the remainder
        for i in range(2, rem + 3):
            f =(f0 + f1)% 60
            f0 = f1
            f1 = f
 
        s = f1-1
        return(s)
 
# Driver code
if __name__ == '__main__':
     
    m = 10087887
    n = 2983097899
 
    final = fib(n)-fib(m-1)
 
    print(final % 10)

// C# program to calculate
// last digit of the sum of the
// fibonacci numbers from M to N
using System;
 
class GFG{
 
// Calculate the sum of the first
// N fibonacci numbers using Pisano
// period
static int fib(long n)
{
     
    // The first two fibonacci numbers
    int f0 = 0;
    int f1 = 1;
 
    // Base case
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    else
    {
         
        // Pisano period for % 10 is 60
        int rem = (int)(n % 60);
 
        // Checking the remainder
        if(rem == 0)
           return 0;
 
        // The loop will range from 2 to
        // two terms after the remainder
        for(int i = 2; i < rem + 3; i++)
        {
           int f = (f0 + f1) % 60;
           f0 = f1;
           f1 = f;
        }
         
        int s = f1 - 1;
        return s;
    }
}
 
// Driver Code
public static void Main()
{
    int m = 10087887;
    long n = 2983097899L;
    int Final = (int)Math.Abs(fib(n) -
                              fib(m - 1));
     
    Console.WriteLine(Final % 10);
}
}
 
// This code is contributed by Code_Mech

<script>
// javascript program to calculate
// last digit of the sum of the
// fibonacci numbers from M to N
 
    // Calculate the sum of the first
    // N Fibonacci numbers using Pisano
    // period
    function fib(n) {
 
        // The first two Fibonacci numbers
        var f0 = 0;
        var f1 = 1;
 
        // Base case
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;
        else {
 
            // Pisano period for % 10 is 60
            var rem = parseInt( (n % 60));
 
            // Checking the remainder
            if (rem == 0)
                return 0;
 
            // The loop will range from 2 to
            // two terms after the remainder
            for (i = 2; i < rem + 3; i++) {
                var f = (f0 + f1) % 60;
                f0 = f1;
                f1 = f;
            }
 
            var s = f1 - 1;
            return s;
        }
    }
 
    // Driver Code
    var m = 10087887;
    var n = 2983097899;
    var Final = parseInt( Math.abs(fib(n) - fib(m - 1)));
 
    document.write(Final % 10);
 
// This code is contributed by Rajput-Ji
</script>

5

Complejidad de tiempo: O(1) , porque este código se ejecuta casi 60 veces para cualquier número de entrada. 

Espacio Auxiliar: O(1)