给定x，k和m，计算（x xxx…k )%m、 x是k次幂。给定x总是素数，m大于x。
null
例如：
Input : 2 3 3Output : 1Explanation : ((2 ^ 2) ^ 2) % 3 = (4 ^ 2) % 3 = 1Input : 3 2 3Output : 0Explanation : (3^3)%3 = 0
A. 缺乏经验的 这种方法是计算xk次的幂，每次都进行模运算。
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; } |
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> |
输出：
2
一 有效解决方案 就是使用 欧拉惯性函数 来解决这个问题。因为x是一个素数，并且总是大于m，这意味着x和m总是共素数。因此，这将有助于 （a^b）%m=（a^b%et（m）））%m ，其中et（m）是 尤拉商数 考虑有一个功能 计算（x，k，m） 这就是价值所在 （x^x^x^x…k次）%m . （x^x^x^x…k次）%m 可以写成 （a^b）%m=（a^b%et（m）））%m 哪里 b=计算（x，k-1，et（m）） .可以编写一个递归函数，基本情况是k=0，则答案为1，如果m=1，则答案为0。
以下是上述方法的实施情况。
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; } |
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> |
输出：
0
时间复杂性 ：O（N），其中N是10 6. 因为所有的Euler Totient值都是预先计算的。 辅助空间： O（N），其中N是10 6.
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
