Grade 12 · Math for programmingCitește în română

Modular exponentiation

Original: Exponențierea modulară

O(log n)C++1749 lines3 examples

The idea

We compute a^n mod m for n up to 10^18. We use the same idea as fast exponentiation, but after every multiplication we take the remainder modulo m: (x * y) mod m = ((x mod m) * (y mod m)) mod m. Since m ≤ 10^9, any product of two remainders is below 10^18 and fits in long long. So the numbers never grow, and the number of steps is just the number of bits of n (at most 60).

Original description (Romanian)

Calculăm a^n mod m pentru n de până la 10^18. Folosim aceeași idee ca la exponențierea rapidă, dar după fiecare înmulțire luăm restul la m: (x * y) mod m = ((x mod m) * (y mod m)) mod m. Cum m ≤ 10^9, orice produs a două resturi este sub 10^18 și încape în long long. Astfel numerele nu cresc niciodată, iar pașii sunt doar câți biți are n (cel mult 60).

Complexity
O(log n)
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input

2 10 1000

Expected output

24
Example 2

Input

3 200 1000000007

Expected output

136318165
Example 3

Input

7 1000000000000000000 1000000007

Expected output

259616729

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

exponentiere-modulara.cpp
/*
 * Titlu: Exponențierea modulară
 * Clasa: 12
 * Capitol: Matematică pentru programare
 * Descriere: Calculăm a^n mod m pentru n de până la 10^18. Folosim aceeași idee ca
 *            la exponențierea rapidă, dar după fiecare înmulțire luăm restul la m:
 *            (x * y) mod m = ((x mod m) * (y mod m)) mod m. Cum m ≤ 10^9, orice
 *            produs a două resturi este sub 10^18 și încape în long long. Astfel
 *            numerele nu cresc niciodată, iar pașii sunt doar câți biți are n
 *            (cel mult 60).
 * Complexitate: O(log n)
 *
 * Exemplu
 * Intrare: 2 10 1000
 * Ieșire: 24
 *
 * Exemplu
 * Intrare: 3 200 1000000007
 * Ieșire: 136318165
 *
 * Exemplu
 * Intrare: 7 1000000000000000000 1000000007
 * Ieșire: 259616729
 */
#include <iostream>
using namespace std;

long long putereModulara(long long baza, long long exponent, long long mod)
{
    long long rezultat = 1 % mod; // pentru mod = 1 rezultatul trebuie să fie 0
    baza = baza % mod;
    while (exponent > 0)
    {
        if (exponent % 2 == 1)
            rezultat = rezultat * baza % mod;
        baza = baza * baza % mod;
        exponent = exponent / 2;
    }
    return rezultat;
}

int main()
{
    long long a, n, m;
    cin >> a >> n >> m;
    cout << putereModulara(a, n, m) << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.