Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Modular Exponentiation

Compute base to the power exponent, modulo a number, with fast exponentiation.

Das lernst du

  • Raise a number to a huge power in O(log exponent) steps
  • Keep every intermediate value reduced to avoid overflow
  • Handle exponent 0 and modulus 1

Problem

Übersetzung anzeigen

Compute base^exponent mod modulus. The exponent can be as large as 10^18, so multiplying by base that many times is impossible; use exponentiation by squaring instead: look at the exponent's binary digits, square the base at every step, and multiply it into the result when the digit is 1. That takes about 60 steps for any exponent here.

Implement modular_exponentiation(base, exponent, modulus).

Reduce base modulo modulus first and after every multiplication. Since modulus ≤ 10^9, the product of two reduced values is below 10^18 and fits in a signed 64-bit integer.

Input

base: The base.

exponent: The power to raise the base to.

modulus: The number to take the remainder by.

Output

Return base^exponent mod modulus, a value from 0 to modulus − 1. Treat base^0 as 1 for every base, including 0, so the answer for exponent 0 is 1 mod modulus.

Einschränkungen

0 ≤ base ≤ 10^18

0 ≤ exponent ≤ 10^18

1 ≤ modulus ≤ 10^9

Beispiele

Beispiel 1
Eingabe:
base = 3
exponent = 13
modulus = 50

Erwartete Ausgabe:
expected = 23
Eingabe:
long long base = 3;
long long exponent = 13;
long long modulus = 50;

Erwartete Ausgabe:
long long expected = 23;
Eingabe:
long base = 3;
long exponent = 13;
long modulus = 50;

Erwartete Ausgabe:
long expected = 23;

Erläuterung

3^13 = 1,594,323, and 1,594,323 = 50 × 31,886 + 23, so the answer is 23.

Beispiel 2
Eingabe:
base = 2
exponent = 10
modulus = 1000

Erwartete Ausgabe:
expected = 24
Eingabe:
long long base = 2;
long long exponent = 10;
long long modulus = 1000;

Erwartete Ausgabe:
long long expected = 24;
Eingabe:
long base = 2;
long exponent = 10;
long modulus = 1000;

Erwartete Ausgabe:
long expected = 24;

Erläuterung

2^10 = 1024, and 1024 mod 1000 = 24.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Look at the exponent one binary digit at a time, starting from the lowest.

Hinweis 2

Square the base at every step and multiply it into the result when the current bit is 1.

Hinweis 3

Start the result at 1 % modulus, so modulus 1 gives 0.

Erwartete Komplexität

O(log exponent) time, O(1) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.