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 = 27Entrada : 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