Calculer la puissance %m de la puissance k

Notre objectif est de calculer k fois %m élevé à la puissance, en prenant en entrée la base, les valeurs de k et m -

Regardez la photo ci-dessus. Avez-vous essayé de calculer un tel problème ? Essayons.

Calculez la puissance élevée à la kième puissance, puis prenez le modulo m.

La traduction chinoise de

Explication

est :

Explication

Dans ce problème, x, k et m sont donnés. Calculez ${x^{x{^x{^{^.{^{^.{^{^.}}}}}}}}}}$, répétez k fois, puis prenez modulo m.

Comprenons-le à travers un exemple.

On sait que x = 2, k = 4, m = 6

Par conséquent, calculez $2^{2^{2{^2}}} :=:4^{2{^2}} :=:16^2:=:256$ p>

Puis 256% 6 = 4.

Donc, le résultat final est 4.

Méthode

Discutons de l'algorithme étape par étape pour calculer k fois la puissance de % m.

• Prenez les valeurs de x, k et m en entrée.

• Utilisez la fonction pow pour calculer la puissance d'une puissance, et enfin utilisez l'opérateur modulo pour obtenir le résultat final.

• Imprimez le résultat final en sortie.

Programme C++ pour calculer la k-ième puissance %m.

#include <iostream>
#include <cmath>
using namespace std;

int powofpow(int x, int k){
   int val = x;
   k--;
   while (k--)
      val = pow(val, x);
 
   return val;
}

int main(){
   int x = 5, k = 2, m = 3;
   int result;
   
   result =  powofpow(x, k);
   result %= m;
   
   cout << "Compute power of power " << k << " times % " << m << " of " << x << " is " << result << endl;
   
   return 0;
}

Sortie

Compute power of power 2 times % 3 of 5 is 2

Complexité

Complexité temporelle : O(k), puisque ce code effectue des itérations (k-1) fois.

Complexité spatiale : O(1) car le code utilise un nombre fixe de variables pour stocker les valeurs d'entrée et les résultats quelle que soit la taille de l'entrée.

Conclusion

Dans cet article, nous essayons d'expliquer la méthode de calcul de base élevée à une puissance k fois modulo m, où les valeurs de base, k et m sont données en entrées. J'espère que cet article vous a aidé à mieux comprendre ce concept.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!