Matemáticasc++móduloaritmética modularexponenciación rápida

Aritmética Modular

Domina las operaciones con módulo, esenciales para competencias de programación

OOI Oaxaca9 de febrero de 20264 min read

¿Qué es el módulo?

La operación módulo (%) devuelve el residuo de la división. Es como un reloj: después de las 12, vuelve al 1.

$17 \mod 5 = 2$ (porque $17 = 3 \times 5 + 2$ )
$10 \mod 3 = 1$
$15 \mod 5 = 0$

Analogía del reloj: Si son las 10 y pasan 5 horas, son las 3 (no las 15). $15 \mod 12 = 3$ .

¿Por qué es tan importante?

En competencias, las respuestas pueden ser enormes (cientos de dígitos). El problema dice: "imprime la respuesta módulo $10^9 + 7$ ". Esto significa que solo necesitas el residuo al dividir entre $10^9 + 7$ .

const int MOD = 1e9 + 7;  // 1000000007 (primo)

Propiedades fundamentales

Las operaciones con módulo se pueden hacer paso a paso:

(a + b) \mod m = ((a \mod m) + (b \mod m)) \mod m

(a \times b) \mod m = ((a \mod m) \times (b \mod m)) \mod m

(a - b) \mod m = ((a \mod m) - (b \mod m) + m) \mod m

⚠️

La resta puede dar negativo en C++. Siempre suma m antes de tomar módulo: ((a - b) % m + m) % m.

¡La división NO funciona así! No puedes hacer $(a / b) \mod m$ . Necesitas el inverso modular (ver más abajo).

Aplicando módulo en la práctica

const int MOD = 1e9 + 7;

// Suma modular
long long sumar(long long a, long long b) {
    return (a + b) % MOD;
}

// Resta modular (cuidado con negativos)
long long restar(long long a, long long b) {
    return ((a - b) % MOD + MOD) % MOD;
}

// Multiplicación modular
long long multiplicar(long long a, long long b) {
    return (a % MOD) * (b % MOD) % MOD;
}

Exponenciación rápida (modular)

Calcular $a^n \mod m$ directamente sería imposible para $n$ grande. Usamos la técnica de exponenciación binaria: $O(\log n)$ .

Idea: $a^{10} = (a^5)^2 = (a^4 \times a)^2 = ((a^2)^2 \times a)^2$

long long potencia(long long base, long long exp, long long mod) {
    long long resultado = 1;
    base %= mod;

    while (exp > 0) {
        if (exp % 2 == 1) {           // Si el exponente es impar
            resultado = resultado * base % mod;
        }
        exp /= 2;                      // Dividir exponente entre 2
        base = base * base % mod;      // Elevar la base al cuadrado
    }

    return resultado;
}

Ejemplo

$2^{10} \mod 1000$ :

Paso	base	exp	resultado
0	2	10	1
1	4	5	1
2	16	2	4 (×4, exp impar)
3	256	1	4
4	...	0	1024 mod 1000 = 24

Inverso modular

Para "dividir" en aritmética modular, multiplicamos por el inverso modular.

$a^{-1} \mod m$ es el número $x$ tal que $a \times x \equiv 1 \pmod{m}$ .

Si $m$ es primo, por el Pequeño Teorema de Fermat: $a^{-1} \equiv a^{m-2} \pmod{m}$

long long inverso(long long a, long long mod) {
    return potencia(a, mod - 2, mod);
}

// División modular: a / b mod m = a * b^(-1) mod m
long long dividir(long long a, long long b, long long mod) {
    return a % mod * inverso(b, mod) % mod;
}

Ejemplo completo: Fibonacci grande

Calcula el N-ésimo Fibonacci módulo $10^9 + 7$ :

#include <iostream>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;

    if (n <= 1) {
        cout << n << endl;
        return 0;
    }

    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long long c = (a + b) % MOD;
        a = b;
        b = c;
    }

    cout << b << endl;
    return 0;
}

Ejercicio de práctica

Calcula $a^b \mod m$ dados a, b y m.

Entrada: 2 100 1000000007 Salida: 976371285

Ver solución

#include <iostream>
using namespace std;

long long potencia(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

int main() {
    long long a, b, m;
    cin >> a >> b >> m;
    cout << potencia(a, b, m) << endl;
    return 0;
}