Dados x, k y m. Calcule (x xxx…k )%m, x está en potencia k veces. Dado que x siempre es primo y m es mayor que x.
Ejemplos:
Input : 2 3 3
Output : 1
Explanation : ((2 ^ 2) ^ 2) % 3
= (4 ^ 2) % 3
= 1
Input : 3 2 3
Output : 0
Explanation : (3^3)%3 = 0
Un enfoque ingenuo es calcular la potencia de xk veces y hacer una operación de módulo cada vez.
C++
// C++ program for computing
// x^x^x^x.. %m
#include <bits/stdc++.h>
using namespace std;
// Function to compute the given value
int calculate(int x, int k, int m)
{
int result = x;
k--;
// compute power k times
while (k--) {
result = pow(result, x);
if (result > m)
result %= m;
}
return result;
}
// Driver Code
int main()
{
int x = 5, k = 2, m = 3;
// Calling function
cout << calculate(x, k, m);
return 0;
}
C
// C program for computing
// x^x^x^x.. %m
#include <stdio.h>
#include <math.h>
// Function to compute the given value
int calculate(int x, int k, int m)
{
int result = x;
k--;
// compute power k times
while (k--) {
result = pow(result, x);
if (result > m)
result %= m;
}
return result;
}
// Driver Code
int main()
{
int x = 5, k = 2, m = 3;
// Calling function
printf("%d",calculate(x, k, m));
return 0;
}
// This code is contributed by kothavvsaakash.
Java
// Java program for computing
// x^x^x^x.. %m
class GFG
{
// Function to compute
// the given value
static int calculate(int x,
int k, int m)
{
int result = x;
k--;
// compute power k times
while (k --> 0)
{
result = (int)Math.pow(result, x);
if (result > m)
result %= m;
}
return result;
}
// Driver Code
public static void main(String args[])
{
int x = 5, k = 2, m = 3;
// Calling function
System.out.println( calculate(x, k, m));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program for # computing x^x^x^x.. %m import math # Function to compute # the given value def calculate(x, k, m): result = x; k = k - 1; # compute power k times while (k): result = math.pow(result, x); if (result > m): result = result % m; k = k - 1; return int(result); # Driver Code x = 5; k = 2; m = 3; # Calling function print(calculate(x, k, m)); # This code is contributed # by mits
C#
// C# program for computing
// x^x^x^x.. %m
using System;
class GFG
{
// Function to compute
// the given value
static int calculate(int x,
int k,
int m)
{
int result = x;
k--;
// compute power
// k times
while (k --> 0)
{
result = (int)Math.Pow(result, x);
if (result > m)
result %= m;
}
return result;
}
// Driver Code
static public void Main ()
{
int x = 5, k = 2, m = 3;
// Calling function
Console.WriteLine(
calculate(x, k, m));
}
}
// This code is contributed
// by ajit
PHP
<?php
// PHP program for computing
// x^x^x^x.. %m
// Function to compute
// the given value
function calculate($x, $k, $m)
{
$result = $x;
$k--;
// compute power k times
while ($k--)
{
$result = pow($result, $x);
if ($result > $m)
$result %= $m;
}
return $result;
}
// Driver Code
$x = 5;
$k = 2;
$m = 3;
// Calling function
echo calculate($x, $k, $m);
// This code is contributed
// by akt_mit
?>
Javascript
<script>
//program for computing
// x^x^x^x.. %m
// Function to compute
// the given value
function calculate(x, k, m)
{
let result = x;
k = k - 1;
// compute power k times
while (k--)
{
result = Math.pow(result, x);
if (result > m)
result %= m;
}
return result;
}
// Driver Code
let x = 5;
let k = 2;
let m = 3;
// Calling function
document.write(calculate(x, k, m));
// This code is contributed
// by sravan kumar
</script>
Producción:
2
Complejidad de tiempo: O(k * logx), donde k y x representan el valor de los enteros dados.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Una solución eficiente es utilizar la Función Totient de Euler para resolver este problema. Dado que x es un número primo y siempre es mayor que m, eso significa que x y m siempre serán coprimos. Entonces, el hecho que ayudará aquí es (a^b)%m = (a^(b % et(m)))%m , donde et(m) es Euler Totient Function . Considere tener una función de cálculo (x, k, m) que proporcione el valor (x^x^x^x…k veces)%m . (x^x^x^x…k veces)%m se puede escribir como (a^b)%m = (a^(b % et(m)))%m , donde b = calcular(x, k- 1, et(m)) . Se puede escribir una función recursiva, con los casos base cuando k=0 entonces, la respuesta es 1, y si m=1, entonces la respuesta es 0.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to compute
// x^x^x^x.. %m
#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
// Create an array to store
// phi or totient values
long long phi[N + 5];
// Function to calculate Euler
// Totient values
void computeTotient()
{
// indicates not evaluated yet
// and initializes for product
// formula.
for (int i = 1; i <= N; i++)
phi[i] = i;
// Compute other Phi values
for (int p = 2; p <= N; p++) {
// If phi[p] is not computed already,
// then number p is prime
if (phi[p] == p) {
// Phi of a prime number p is
// always equal to p-1.
phi[p] = p - 1;
// Update phi values of all
// multiples of p
for (int i = 2 * p; i <= N; i += p) {
// Add contribution of p to its
// multiple i by multiplying with
// (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// Iterative Function to calculate (x^y)%p in O(log y)
long long power(long long x, long long y, long long p)
{
long long res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to 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; // y = y/2
x = (x * x) % p;
}
return res;
}
// Function to calculate
// (x^x^x^x...k times)%m
long long calculate(long long x, long long k,
long long mod)
{
// to store different mod values
long long arr[N];
long long count = 0;
while (mod > 1) {
arr[count++] = mod;
mod = phi[mod];
}
long long result = 1;
long long loop = count + 1;
arr[count] = 1;
// run loop in reverse to calculate
// result
for (int i = min(k, loop) - 1; i >= 0; i--)
result = power(x, result, arr[i]);
return result;
}
// Driver Code
int main()
{
// compute euler totient function values
computeTotient();
long long x = 3, k = 2, m = 3;
// Calling function to compute answer
cout << calculate(x, k, m) << endl;
return 0;
}
C
// C program to compute
// x^x^x^x.. %m
#include <stdio.h>
#define N 1000000
// Create an array to store
// phi or totient values
long long phi[N + 5];
// Function to calculate Euler
// Totient values
int min(int a, int b)
{
int min = a;
if(min > b)
min = b;
return min;
}
void computeTotient()
{
// indicates not evaluated yet
// and initializes for product
// formula.
for (int i = 1; i <= N; i++)
phi[i] = i;
// Compute other Phi values
for (int p = 2; p <= N; p++) {
// If phi[p] is not computed already,
// then number p is prime
if (phi[p] == p) {
// Phi of a prime number p is
// always equal to p-1.
phi[p] = p - 1;
// Update phi values of all
// multiples of p
for (int i = 2 * p; i <= N; i += p) {
// Add contribution of p to its
// multiple i by multiplying with
// (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// Iterative Function to calculate (x^y)%p in O(log y)
long long power(long long x, long long y, long long p)
{
long long res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to 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; // y = y/2
x = (x * x) % p;
}
return res;
}
// Function to calculate
// (x^x^x^x...k times)%m
long long calculate(long long x, long long k,
long long mod)
{
// to store different mod values
long long arr[N];
long long count = 0;
while (mod > 1) {
arr[count++] = mod;
mod = phi[mod];
}
long long result = 1;
long long loop = count + 1;
arr[count] = 1;
// run loop in reverse to calculate
// result
for (int i = min(k, loop) - 1; i >= 0; i--)
result = power(x, result, arr[i]);
return result;
}
// Driver Code
int main()
{
// compute euler totient function values
computeTotient();
long long x = 3, k = 2, m = 3;
// Calling function to compute answer
printf("%lld\n",calculate(x, k, m));
return 0;
}
// This code is contributed by kothavvsaakash.
Java
// Java program for computing
// x^x^x^x.. %m
class GFG
{
// Create an array to store
// phi or totient values
static int N = 1000000;
static long phi[] = new long[N + 5];
// Function to calculate
// Euler Totient values
static void computeTotient()
{
// indicates not evaluated
// yet and initializes for
// product formula.
for (int i = 1; i <= N; i++)
phi[i] = i;
// Compute other Phi values
for (int p = 2; p <= N; p++)
{
// If phi[p] is not
// computed already,
// then number p is prime
if (phi[p] == p)
{
// Phi of a prime number p
// is always equal to p-1.
phi[p] = p - 1;
// Update phi values of
// all multiples of p
for (int i = 2 * p; i <= N; i += p)
{
// Add contribution of p
// to its multiple i by
// multiplying with (1 - 1/p)
phi[i] = (phi[i] / p) *
(p - 1);
}
}
}
}
// Iterative Function to
// calculate (x^y)%p in O(log y)
static long power(long x, long y, long p)
{
long res = 1; // Initialize result
x = x % p; // Update x if it is
// more than or equal to p
while (y > 0)
{
// If y is odd, multiply
// x with result
if ((y & 1) > 0)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Function to calculate
// (x^x^x^x...k times)%m
static long calculate(long x, long k,
long mod)
{
// to store different
// mod values
long arr[] = new long[N];
long count = 0;
while (mod > 1)
{
arr[(int)count++] = mod;
mod = phi[(int)mod];
}
long result = 1;
long loop = count + 1;
arr[(int)count] = 1;
// run loop in reverse
// to calculate result
for (int i = (int)Math.min(k, loop) - 1;
i >= 0; i--)
result = power(x, result, arr[i]);
return result;
}
// Driver Code
public static void main(String args[])
{
// compute euler totient
// function values
computeTotient();
long x = 3, k = 2, m = 3;
// Calling function
// to compute answer
System.out.println(calculate(x, k, m));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to compute # x^x^x^x.. %m N = 1000000 # Create an array to store # phi or totient values phi=[0 for i in range(N + 5)] # Function to calculate Euler # Totient values def computeTotient(): # indicates not evaluated yet # and initializes for product # formula. for i in range(1, N+1): phi[i] = i # Compute other Phi values for p in range(2, N+1): # If phi[p] is not computed already, # then number p is prime if (phi[p] == p): # Phi of a prime number p is # always equal to p-1. phi[p] = p - 1 # Update phi values of all # multiples of p for i in range(2*p, N+1, p): # Add contribution of p to its # multiple i by multiplying with # (1 - 1/p) phi[i] = (phi[i] // p) * (p - 1) # Iterative Function to calculate (x^y)%p in O(log y) def power(x, y, p): res = 1 # Initialize result x = x % p # Update x if it is more than or # equal to 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 # y = y/2 x = (x * x) % p return res # Function to calculate # (x^x^x^x...k times)%m def calculate(x, k,mod): # to store different mod values arr=[0 for i in range(N)] count = 0 while (mod > 1): arr[count] = mod count+=1 mod = phi[mod] result = 1 loop = count + 1 arr[count] = 1 # run loop in reverse to calculate # result for i in range(min(k,loop),-1,-1): result = power(x, result, arr[i]) return result # Driver Code # compute euler totient function values computeTotient() x = 3 k = 2 m = 3 # Calling function to compute answer print(calculate(x, k, m)) # This code is contributed by mohit kumar 29
C#
// C# program for computing
// x^x^x^x.. %m
using System;
class GFG
{
// Create an array to store
// phi or totient values
static int N = 1000000;
static long []phi = new long[N + 5];
// Function to calculate
// Euler Totient values
static void computeTotient()
{
// indicates not evaluated
// yet and initializes for
// product formula.
for (int i = 1; i <= N; i++)
phi[i] = i;
// Compute other Phi values
for (int p = 2; p <= N; p++)
{
// If phi[p] is not
// computed already,
// then number p is prime
if (phi[p] == p)
{
// Phi of a prime
// number p is
// always equal
// to p-1.
phi[p] = p - 1;
// Update phi values
// of all multiples
// of p
for (int i = 2 * p;
i <= N; i += p)
{
// Add contribution of p
// to its multiple i by
// multiplying with (1 - 1/p)
phi[i] = (phi[i] / p) *
(p - 1);
}
}
}
}
// Iterative Function to
// calculate (x^y)%p in O(log y)
static long power(long x,
long y, long p)
{
long res = 1; // Initialize result
x = x % p; // Update x if it
// is more than or
// equal to p
while (y > 0)
{
// If y is odd, multiply
// x with result
if ((y & 1) > 0)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Function to calculate
// (x^x^x^x...k times)%m
static long calculate(long x, long k,
long mod)
{
// to store different
// mod values
long []arr = new long[N];
long count = 0;
while (mod > 1)
{
arr[(int)count++] = mod;
mod = phi[(int)mod];
}
long result = 1;
long loop = count + 1;
arr[(int)count] = 1;
// run loop in reverse
// to calculate result
for (int i = (int)Math.Min(k, loop) - 1;
i >= 0; i--)
result = power(x, result,
arr[i]);
return result;
}
// Driver Code
static public void Main ()
{
// compute euler totient
// function values
computeTotient();
long x = 3, k = 2, m = 3;
// Calling function
// to compute answer
Console.WriteLine(calculate(x, k, m));
}
}
// This code is contributed
// by akt_mit
Javascript
<script>
// Javascript program for computing x^x^x^x.. %m
// Create an array to store
// phi or totient values
let N = 1000000;
let phi = new Array(N + 5);
phi.fill(0);
// Function to calculate
// Euler Totient values
function computeTotient()
{
// indicates not evaluated
// yet and initializes for
// product formula.
for (let i = 1; i <= N; i++)
phi[i] = i;
// Compute other Phi values
for (let p = 2; p <= N; p++)
{
// If phi[p] is not
// computed already,
// then number p is prime
if (phi[p] == p)
{
// Phi of a prime number p
// is always equal to p-1.
phi[p] = p - 1;
// Update phi values of
// all multiples of p
for (let i = 2 * p; i <= N; i += p)
{
// Add contribution of p
// to its multiple i by
// multiplying with (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// Iterative Function to
// calculate (x^y)%p in O(log y)
function power(x, y, p)
{
let res = 1; // Initialize result
x = x % p; // Update x if it is
// more than or equal to p
while (y > 0)
{
// If y is odd, multiply
// x with result
if ((y & 1) > 0)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Function to calculate
// (x^x^x^x...k times)%m
function calculate(x, k, mod)
{
// to store different
// mod values
let arr = new Array(N);
arr.fill(0);
let count = 0;
while (mod > 1)
{
arr[count++] = mod;
mod = phi[mod];
}
let result = 1;
let loop = count + 1;
arr[count] = 1;
// run loop in reverse
// to calculate result
for (let i = Math.min(k, loop) - 1; i >= 0; i--)
result = power(x, result, arr[i]);
return result;
}
// compute euler totient
// function values
computeTotient();
let x = 3, k = 2, m = 3;
// Calling function
// to compute answer
document.write(calculate(x, k, m));
// This code is contributed by rameshtravel07.
</script>
Producción:
0
Complejidad temporal : O(N), donde N es 10 6 ya que todos los valores de Euler Totient están precalculados.
Espacio Auxiliar: O(N), donde N es 10 6
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA