Algorithmes et Structures de Données

Exponentiation binaire

Étant donné 3 nombres x, n et m, vous devez calculer la valeur de .

Entrée

La seule ligne d’entrée contient 3 entiers x, n et m (1 ≤ x, n, m ≤ ).

Sortie

Le programme doit afficher le résultat de l’expression .

Exemples

Entrée
Sortie
2 10 5
4

Explication

  1. 2^10 = 1024 ⇒ 1024 mod 5 = 4
 

Tutoriel

Comme tous les nombres peuvent être très grands, il est nécessaire d’utiliser un algorithme rapide pour s’assurer qu’il s’exécute suffisamment vite. L’exponentiation binaire est un moyen efficace de calculer des puissances élevées d’un nombre. Cette méthode réduit le nombre de multiplications nécessaires pour trouver la puissance, ce qui la rend plus rapide que la méthode traditionnelle consistant à boucler de 1 jusqu’à n et à multiplier le résultat par x.
 
L’algorithme d’exponentiation binaire repose sur l’observation mathématique suivante : si on a un nombre x élevé à la puissance n, alors peut se représenter ainsi :
  • si n est pair
  • si n est impair
Cela accélère considérablement le calcul, car on peut d’abord calculer une seule fois , puis multiplier les résultats entre eux. L’algorithme peut donc ressembler à ceci :
def binpow(x, n, m):
    if n == 0:                        # Cas de base : x^0 = 1
        return 1
    if n % 2 == 0:                    # n est pair ⇒ on calcule la moitié puis on multiplie
        half = binpow(x, n // 2, m)   # on calcule la moitié
        return (half * half) % m      # res = x^(n/2) * x^(n/2)

    # n est impair ⇒ res = x * x^(n-1)
    return (x * binpow(x, n - 1, m)) % m
Grâce à l’exponentiation binaire, on réduit la complexité en passant de à , car on divise n par 2 à chaque itération lorsque n est pair. Il est important de noter qu’à chaque fois que n est impair, l’itération suivante se fait ensuite sur n - 1, qui est pair.
Illustrons l’algorithme sur quelques exemples :
x = 2, n = 10 (on ignore m pour simplifier)
  1. [n = 10] → n % 2 == 0 ⇒ on calcule binpow(2, 5)
  1. [n = 5] → n % 2 ≠ 0 ⇒ on renvoie 2 * binpow(2, 4)
  1. [n = 4] → n % 2 == 0 ⇒ on calcule binpow(2, 2)
  1. [n = 2] → n % 2 == 0 ⇒ on calcule binpow(2, 1)
  1. [n = 1] ⇒ n % 2 ≠ 0 ⇒ on renvoie 2 * binpow(2, 0)
  1. [n = 0] ⇒ n == 0 ⇒ on renvoie 1
  1. [remontée à n = 1] ⇒ on renvoie 2 * 1 = 2
  1. [remontée à n = 2] ⇒ on renvoie 2 * 2 = 4
  1. [remontée à n = 4] ⇒ on renvoie 4 * 4 = 16
  1. [remontée à n = 5] ⇒ on renvoie 2 * 16 = 32
  1. [remontée à n = 10] ⇒ on renvoie 32 * 32 = 1024
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue