Poder de Fibonacci

Dado un número n. Debe encontrar ( Fib(n) ^ Fib(n) ) % 10^9 + 7, donde Fib(n) es el enésimo número de Fibonacci.

Ejemplos: 

Entrada : n = 4 
Salida : 27  El
cuarto número de Fibonacci es 3 
[fib(4) ^ fib(4)] % 10^9 + 7 = (3 ^ 3) % 10^9 + 7 = 27 

Entrada : n = 3 
Salida : 4  El
tercer número de Fibonacci es 2 
[fib(3) ^ fib(3)] % 10^9 + 7 = (2 ^ 2) % 10^9 + 7 = 4 

Si n es grande, fib(n) será enorme y fib(n) ^ fib(n) no solo es difícil de calcular sino que su almacenamiento es imposible.

Enfoque: 
( a ^ (p-1) ) % p = 1 donde p es un número primo (usando el pequeño teorema de Fermat). 
( a ^ a ) % m se puede escribir como ( ( a % m ) ^ a ) % m 
También es posible escribir cualquier número ‘a’ como a = k * ( m – 1 ) + r (usando el algoritmo de división) 
donde ‘k’ es cociente y ‘r’ es resto. Podemos decir que r = a % (m-1) 
Entonces, Pasos para reducir nuestro cálculo, supongamos a = fib(n) 

  ( a ^ a ) % m 
= ( ( a % m ) ^ a ) % m 
= ( ( a % m ) ^ ( k * ( m - 1 ) + r ) ) % m 
= ( ( ( a % m ) ^ ( m-1 ) ) ^ k  * ( a % m ) ^ r ) % m
= ( (1 ^ k) * ( a % m ) ^ r ) % m
= ( ( a % m ) ^ r ) % m   
= ( ( a % m ) ^ (a % (m-1) ) % m 

un % my un % (m-1) son fáciles de calcular y almacenar. 
y podemos calcular ( x ^ y ) % m usando este artículo de GFG. 
Podemos encontrar el n -ésimo número de fibonacci en el tiempo log(n) usando este artículo de GFG.

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

C++

#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
  
// Iterative function to compute modular power
long long modularexpo(long long x, long long y, long long p)
{
    // Initialize result
    long long res = 1;
    // Update x if it is more than or
    // equal to p
    x = x % p;
  
    while (y > 0) {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;
  
        // y must be even now
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
// Helper function that multiplies 2 matrices
// F and M of size 2*2, and puts the
// multiplication result back to F[][]
void multiply(long long F[2][2], long long M[2][2], long long m)
{
    long long x = ((F[0][0] * M[0][0]) % m +
                   (F[0][1] * M[1][0]) % m) % m;
 
    long long y = ((F[0][0] * M[0][1]) % m +
                   (F[0][1] * M[1][1]) % m) % m;
 
    long long z = ((F[1][0] * M[0][0]) % m +
                   (F[1][1] * M[1][0]) % m) % m;
 
    long long w = ((F[1][0] * M[0][1]) % m +
                   (F[1][1] * M[1][1]) % m) % m;
  
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}
 
// Helper function that calculates F[][] raise to
// the power n and puts the  result in F[][]
// Note that this function is designed only for fib()
// and won't work as general power function
void power(long long F[2][2], long long n, long long m)
{
    if (n == 0 || n == 1)
        return;
    long long M[2][2] = { { 1, 1 }, { 1, 0 } };
  
    power(F, n / 2, m);
    multiply(F, F, m);
  
    if (n % 2 != 0)
        multiply(F, M, m);
}
 
// Function that returns nth Fibonacci number
long long fib(long long n, long long m)
{
    long long F[2][2] = { { 1, 1 }, { 1, 0 } };
    if (n == 0)
        return 0;
    power(F, n - 1, m);
    return F[0][0];
}
 
// Driver Code
int main()
{
    long long n = 4;
    long long base = fib(n, mod) % mod;
    long long expo = fib(n, mod - 1) % (mod - 1);
    long long result = modularexpo(base, expo, mod) % mod;
    cout << result << endl;
}

Java

class GFG
{
static int mod = 1000000007;
 
// Iterative function to compute modular power
static long modularexpo(long x, long y, long p)
{
    // Initialize result
    long res = 1;
     
    // Update x if it is more than or
    // equal to p
    x = x % p;
 
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y % 2 == 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
// Helper function that multiplies 2 matrices
// F and M of size 2*2, and puts the
// multiplication result back to F[][]
static void multiply(long F[][],
                     long M[][], long m)
{
    long x = ((F[0][0] * M[0][0]) % m +
              (F[0][1] * M[1][0]) % m) % m;
 
    long y = ((F[0][0] * M[0][1]) % m +
              (F[0][1] * M[1][1]) % m) % m;
 
    long z = ((F[1][0] * M[0][0]) % m +
              (F[1][1] * M[1][0]) % m) % m;
 
    long w = ((F[1][0] * M[0][1]) % m +
              (F[1][1] * M[1][1]) % m) % m;
 
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}
 
// Helper function that calculates F[][] raise to
// the power n and puts the result in F[][]
// Note that this function is designed only for fib()
// and won't work as general power function
static void power(long F[][], long n, long m)
{
    if (n == 0 || n == 1)
        return;
    long M[][] = { { 1, 1 }, { 1, 0 } };
 
    power(F, n / 2, m);
    multiply(F, F, m);
 
    if (n % 2 != 0)
        multiply(F, M, m);
}
 
// Function that returns nth Fibonacci number
static long fib(long n, long m)
{
    long F[][] = { { 1, 1 }, { 1, 0 } };
    if (n == 0)
        return 0;
    power(F, n - 1, m);
    return F[0][0];
}
 
// Driver Code
public static void main(String[] args)
{
    long n = 4;
    long base = fib(n, mod) % mod;
    long expo = fib(n, mod - 1) % (mod - 1);
    long result = modularexpo(base, expo, mod) % mod;
    System.out.println(result);
}
}
 
// This code is contributed by PrinciRaj1992

Python3

mod = 1000000007;
 
# Iterative function to compute modular power
def modularexpo(x, y, p):
 
    # Initialize result
    res = 1;
     
    # Update x if it is more than or
    # equal to p
    x = x % p;
 
    while (y > 0):
         
        # If y is odd, multiply x with result
        if (y & 1):
            res = (res * x) % p;
 
        # y must be even now
        y = y >> 1;
        x = (x * x) % p;
     
    return res;
 
# Helper function that multiplies 2 matrices
# F and M of size 2*2, and puts the
# multiplication result back to F[][]
def multiply(F, M, m):
 
    x = ((F[0][0] * M[0][0]) % m +
         (F[0][1] * M[1][0]) % m) % m;
 
    y = ((F[0][0] * M[0][1]) % m +
         (F[0][1] * M[1][1]) % m) % m;
 
    z = ((F[1][0] * M[0][0]) % m +
         (F[1][1] * M[1][0]) % m) % m;
 
    w = ((F[1][0] * M[0][1]) % m +
         (F[1][1] * M[1][1]) % m) % m;
 
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
 
# Helper function that calculates F[][] raise to
# the power n and puts the result in F[][]
# Note that this function is designed only for fib()
# and won't work as general power function
def power(F, n, m):
 
    if (n == 0 or n == 1):
        return;
    M = [[ 1, 1 ], [ 1, 0 ]];
 
    power(F, n // 2, m);
    multiply(F, F, m);
 
    if (n % 2 != 0):
        multiply(F, M, m);
 
# Function that returns nth Fibonacci number
def fib(n, m):
 
    F = [[ 1, 1 ], [ 1, 0 ]];
    if (n == 0):
        return 0;
    power(F, n - 1, m);
    return F[0][0];
 
# Driver Code
if __name__ == '__main__':
    n = 4;
    base = fib(n, mod) % mod;
    expo = fib(n, mod - 1) % (mod - 1);
    result = modularexpo(base, expo, mod) % mod;
    print(result);
 
# This code is contributed by 29AjayKumar

C#

using System;
 
class GFG
{
static int mod = 1000000007;
 
// Iterative function to compute modular power
static long modularexpo(long x, long y, long p)
{
    // Initialize result
    long res = 1;
     
    // Update x if it is more than or
    // equal to p
    x = x % p;
 
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y % 2 == 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
// Helper function that multiplies 2 matrices
// F and M of size 2*2, and puts the
// multiplication result back to F[,]
static void multiply(long [,]F,
                     long [,]M, long m)
{
    long x = ((F[0, 0] * M[0, 0]) % m +
              (F[0, 1] * M[1, 0]) % m) % m;
 
    long y = ((F[0, 0] * M[0, 1]) % m +
              (F[0, 1] * M[1, 1]) % m) % m;
 
    long z = ((F[1, 0] * M[0, 0]) % m +
              (F[1, 1] * M[1, 0]) % m) % m;
 
    long w = ((F[1, 0] * M[0, 1]) % m +
              (F[1, 1] * M[1, 1]) % m) % m;
 
    F[0, 0] = x;
    F[0, 1] = y;
    F[1, 0] = z;
    F[1, 1] = w;
}
 
// Helper function that calculates F[,] raise to
// the power n and puts the result in F[,]
// Note that this function is designed only for fib()
// and won't work as general power function
static void power(long [,]F, long n, long m)
{
    if (n == 0 || n == 1)
        return;
    long [,]M = { { 1, 1 }, { 1, 0 } };
 
    power(F, n / 2, m);
    multiply(F, F, m);
 
    if (n % 2 != 0)
        multiply(F, M, m);
}
 
// Function that returns nth Fibonacci number
static long fib(long n, long m)
{
    long [,]F = { { 1, 1 }, { 1, 0 } };
    if (n == 0)
        return 0;
    power(F, n - 1, m);
    return F[0, 0];
}
 
// Driver Code
public static void Main(String[] args)
{
    long n = 4;
    long Base = fib(n, mod) % mod;
    long expo = fib(n, mod - 1) % (mod - 1);
    long result = modularexpo(Base, expo, mod) % mod;
    Console.WriteLine(result);
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
let mod = 1000000007;
 
// Iterative function to compute modular power
function modularexpo(x, y, p)
{
     
    // Initialize result
    let res = 1;
     
    // Update x if it is more than or
    // equal to p
    x = x % p;
 
    while (y > 0)
    {
         
        // If y is odd, multiply x with result
        if (y % 2 == 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
// Helper function that multiplies 2 matrices
// F and M of size 2*2, and puts the
// multiplication result back to F[][]
function multiply(F, M, m)
{
    let x = ((F[0][0] * M[0][0]) % m +
             (F[0][1] * M[1][0]) % m) % m;
 
    let y = ((F[0][0] * M[0][1]) % m +
             (F[0][1] * M[1][1]) % m) % m;
 
    let z = ((F[1][0] * M[0][0]) % m +
             (F[1][1] * M[1][0]) % m) % m;
 
    let w = ((F[1][0] * M[0][1]) % m +
             (F[1][1] * M[1][1]) % m) % m;
 
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}
 
// Helper function that calculates F[][] raise to
// the power n and puts the result in F[][]
// Note that this function is designed only for fib()
// and won't work as general power function
function power(F, n, m)
{
    if (n == 0 || n == 1)
        return;
         
    let M = [ [ 1, 1 ], [ 1, 0 ] ];
     
    power(F, Math.floor(n / 2), m);
    multiply(F, F, m);
 
    if (n % 2 != 0)
        multiply(F, M, m);
}
 
// Function that returns nth Fibonacci number
function fib(n, m)
{
    let F = [ [ 1, 1 ], [ 1, 0 ] ];
    if (n == 0)
        return 0;
         
    power(F, n - 1, m);
    return F[0][0];
}
 
// Driver Code
let n = 4;
let base = fib(n, mod) % mod;
let expo = fib(n, mod - 1) % (mod - 1);
let result = modularexpo(base, expo, mod) % mod;
 
document.write(result);
 
// This code is contributed by code_hunt
 
</script>
Producción: 

27

 

Complejidad de tiempo: log(n)

Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por Vidhayak_Chacha 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 *