10 · Algoritmos numéricos y aritmética modular

Buscar soluciones eficientes · Ruta de Aprendizaje

Antes de empezar. Ciclos, funciones y el operador resto %: 00 - Programar desde cero; vectores: 03 - Arreglos y búsqueda lineal.

🎯 Objetivos

Al terminar este módulo sabes:

  • Dominar %: dígitos, ciclos, y el caso traicionero de los negativos.
  • Testear primalidad en O(√n) y calcular MCD/MCM respetando los límites numéricos.
  • Trabajar módulo 10⁹+7 y elevar a potencias gigantes en O(log e).

📖 La lección

Esta clase tiene tres preguntas: ¿dónde quedo tras dar vueltas?, ¿qué divisores comparten dos números? y ¿cómo calcular potencias sin multiplicar una vez por cada unidad del exponente?. Cada tramo desarrolla una herramienta distinta.

El operador % a fondo

Antes de nada, una imagen que sirve para todo el módulo: trabajar módulo M es trabajar en un reloj de M horas. Al llegar a M, vuelves al 0.

012347 % 5 = 2una vuelta + 2contar 7 pasos desde el 0 termina en el 2

Si el diagrama no cabe, deslízalo horizontalmente.

Por eso 7 % 5 es 2: das una vuelta completa (5) y te sobran 2.

Desarmar un número en dígitos. n % 10 te da el último dígito y n / 10 te lo quita. Sigue la traza con 4025:

pasonn % 10 (el dígito)n / 10 (lo que queda)
140255402
2402240
34004
4440 ← se acabó

Los dígitos salen al revés (5, 2, 0, 4). Si los necesitas en orden, guárdalos y da vuelta el arreglo.

El caso traicionero: los negativos. En C++, -7 % 3 NO es 2, es −1. La razón es que la división entera trunca hacia el cero:

7 % 3-7 % 3
C++ calcula primero7 / 3 = 2-7 / 3 = −2 (no −3: trunca hacia el 0)
y después el resto7 − 3·2 = 1−7 − 3·(−2) = −1
lo que casi siempre querías1 ✅2 ❌

En un reloj de tres posiciones, −7 equivale a retroceder una posición después de descontar dos vueltas completas: llegas al 2. El resto −1 representa esa misma posición, escrita de otra forma. El arreglo es darle una vuelta completa:

En este ejemplo usamos 1 <= m <= 10⁹+7, de modo que sumar m al resto cabe en long long.

long long mod_positivo(long long x, long long m) {
    return ((x % m) + m) % m; // -7 -> -1 -> -1+3 = 2 ✅
}

Cuando el problema resta cosas módulo m, ese envoltorio evita respuestas negativas fantasma. Es de los errores que más caro salen porque el código se ve bien.

Primalidad en O(√n)

Un divisor de n lo divide sin resto. Un entero primo es mayor que 1 y sus únicos divisores positivos son 1 y él mismo: 7 es primo; 12 no, porque 3·4=12. El 1 no es primo. Queremos decidirlo sin probar todos los números menores que n.

La regla se enuncia así: “basta probar divisores hasta √n”. Y suena a magia hasta que la dibujas. Mira todos los divisores de 36, emparejados:

1 × 362 × 183 × 124 × 9123491218366√36 = 6cada divisor chico tiene un socio grande, y el par se refleja en la raíz

Si el diagrama no cabe, deslízalo horizontalmente.

Los divisores vienen de a pares, y cada par se refleja en √n. Uno es menor o igual que la raíz y el otro mayor o igual. En 36, el par central es 6×6: hay que incluir la igualdad. Buscamos divisores desde 2, porque el par trivial 1×n existe incluso cuando n es primo. Si un compuesto tuviera un divisor grande, tendría también un socio entre 2 y √n.

bool es_primo(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i * i <= n; i++)   // i*i <= n es "i <= raíz de n"
        if (n % i == 0) return false;        // lo pillamos: tiene socio
    return true;
}

Fíjate en i * i <= n en vez de i <= sqrt(n): evita los decimales, que en números grandes redondean mal y te hacen perder un caso. Aquí suponemos n <= 10¹², por lo que i*i cabe en long long. El costo sigue siendo O(√n): aumentar mucho n o hacer muchas consultas puede volverlo demasiado lento.

¿Y si necesitas muchos primos chicos en vez de uno grande?

Lo que necesitasQué usarCosto
¿este número es primo? (uno grande)probar hasta la raízO(√n)
todos los primos hasta n (muchos chicos)criba de EratóstenesO(n log log n)
en qué primos se descomponeFactorizaciónO(√n)

MCD y MCM

El máximo común divisor tiene un dibujo exacto: mcd(48, 18) es el lado del cuadrado más grande con que puedes embaldosar un rectángulo de 48×18 sin cortar ninguna baldosa. Y el algoritmo de Euclides es literalmente ir sacando el cuadrado más grande que quepa, una y otra vez, hasta que lo que sobra sea un cuadrado perfecto.

181812664818el cuadrado más chico que aparece es 6 = mcd(48, 18)

Si el diagrama no cabe, deslízalo horizontalmente.

En números, sigue la traza:

pasoaba % b (lo que sobra)
1481848 % 18 = 12
2181218 % 12 = 6
312612 % 6 = 0
460b llegó a 0 → la respuesta es 6

En cada paso el par se hace más chico, y b termina siempre en 0. Lo que queda en a es el MCD.

¿Por qué conserva el MCD? Como 48 = 2·18 + 12, cualquier divisor de 48 y 18 también divide 12. A la inversa, un divisor de 18 y 12 divide 2·18+12=48. Por tanto, los divisores comunes de (48,18) y (18,12) son exactamente los mismos. Cada paso de Euclides conserva esa información y reduce el segundo número.

El mínimo común múltiplo es el menor entero positivo divisible por ambos números. Para 48 y 18 es 144. Para ver de dónde sale, con 6 y 8 tenemos MCD 2: 6=2·3 y 8=2·4. Los factores restantes 3 y 4 no comparten divisores mayores que 1. Un múltiplo común mínimo necesita el factor común una vez y ambos restantes: 2·3·4=24. Multiplicar 6·8 contaría dos veces ese factor común. Por eso se obtiene con a / mcd(a,b) * b. En este ejemplo a y b son positivos y el MCM debe caber en long long.

long long mcd(long long a, long long b) {
    while (b != 0) { a %= b; swap(a, b); } // Euclides iterativo
    return a;
}
// Divide ANTES de multiplicar; el resultado debe caber en long long
// supone: long long a, b;  // a > 0, b > 0
long long mcm = a / mcd(a, b) * b;

C++17 trae gcd(a, b) y lcm(a, b) listos, pero saber Euclides es parte del oficio (la teoría, en Euclides extendido (gcd)). El orden a / mcd * b importa: a * b primero puede desbordar aunque el MCM quepa perfectamente.

Aritmética modular

A veces solo piden el resto de una respuesta muy grande al dividirla por M. Antes de aplicar ese requisito, construyamos la potencia que queremos calcular.

Agrupar factores antes de programar

3⁶ son seis factores 3. Agruparlos por parejas da (3²)³: hacer un cuadrado deja la mitad de factores pendientes. Si el exponente es impar, separamos un factor primero: 3¹³ = 3 · (3²)⁶.

Guardaremos en r lo que ya separamos, en b el factor actual y en e cuántas copias de ese factor faltan. Al principio r=1, b=3, e=13.

SituaciónProducto que todavía representa la respuesta
inicio1 · 3¹³
separar un factor porque 13 es impar3 · 3¹²
agrupar los doce factores por parejas3 · 9⁶
agrupar de nuevo (6 es par)3 · 81³
separar un 81 y agrupar los otros dos243 · 6561¹
incorporar el último factor1594323 · 1

Ese producto r · b^e se conserva en cada paso. Con e=0 ya no quedan factores por incorporar y r es la respuesta. No hay que multiplicar trece veces: el exponente se reduce a la mitad en cada vuelta.

Conservar solo el resto

Para M=1000, 1594323 deja resto 323. Podemos reducir después de cada suma o producto: por ejemplo, 6561 y 561 difieren en seis vueltas completas de 1000, y multiplicarlos por 243 también produce resultados que difieren en vueltas completas. Así, (243 * 6561) % 1000 y (243 * 561) % 1000 dan 323.

El módulo no cambia las decisiones de paridad del exponente; solo limita los valores guardados en r y b. El producto se calcula antes de aplicar %, por lo que también debe caber en el tipo. Ahora traducimos los pasos a C++:

La función siguiente supone b >= 0, e >= 0 y 2 <= M <= 10⁹+7. Así los productos de dos residuos caben en long long. Si necesitas una base negativa, normalízala con mod_positivo antes de llamar.

long long potmod(long long b, long long e, long long M) {
    long long r = 1;
    b %= M;
    while (e > 0) {
        if (e % 2 == 1) r = r * b % M; // exponente impar: multiplica una vez
        b = b * b % M;                 // cuadrado en cada paso
        e /= 2;                        // y la mitad del exponente
    }
    return r;
}

La traza de potmod(3, 13, 1000) — o sea 3¹³ módulo 1000:

e¿impar?r (la respuesta que se arma)b (se va elevando al cuadrado)
13sí → multiplica1 · 3 = 33² = 9
6no39² = 81
3sí → multiplica3 · 81 = 24381² = 6561 → 561
1sí → multiplica243 · 561 = 136323 → 323—
0fin323

Y acá está lo bonito:

841el exponente 13 se arma con potencias de 2……y potmod multiplica justo en esos tres pasos: 3⁸ · 3⁴ · 3¹ = 3¹³

Si el diagrama no cabe, deslízalo horizontalmente.

Lo que descomponemos como suma de potencias de dos es el exponente: 13 = 8+4+1. La potencia resulta de un producto: 3¹³ = 3⁸·3⁴·3. Durante el ciclo, r · b^e conserva el resultado buscado módulo M: si e es impar, se pasa un factor b a r; después se agrupan por parejas los factores restantes.

Para 2⁶⁰, el exponente recorre 60,30,15,7,3,1: son seis vueltas, con seis cuadrados y cuatro multiplicaciones en r. Un exponente cercano a 2⁶⁰ sí requeriría unas 60 vueltas. Ficha completa: Exponenciación rápida (modular).

(La división modular es otra historia — y el Syllabus IOI la deja explícitamente fuera.)

🏋️ Práctica

Práctica directa: Tres herramientas numéricas

Prueba tres casos nuevos: retroceder 4 desde 1 en un reloj de 6 posiciones; calcular MCD(30,18) y MCM(30,18); calcular 2¹⁰ módulo 100. Resultados: 3; 6 y 90; 24.

Variación: Coincidir otra vez

Dos luces parpadean cada a y b segundos y coinciden en el instante 0. Calcula cuándo volverán a coincidir, con 1 ≤ a,b ≤ 10⁹. Para 6 y 8, la respuesta es 24; para 7 y 7, es 7.

Aplicar en problemas

Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.

Problemas OCI reales, en español (cada nota trae el link a su mirror):

#ProblemaFaseQué practica
1El candado del basureroNacional 2019distancias en aritmética módulo 10
2Daniela y los múltiplosRegional 2022múltiplos con saltos
3BalancínNacional 2023el MCD resolviendo una ecuación
4⭐ Gollum vs GolombNacional 2015recurrencias con n hasta 10¹⁰ y long long
5⭐⭐ CataloniaNacional 2020coordenadas en espiral hexagonal hasta 10¹⁸

Más aplicaciones (en inglés)

#ProblemaDificultadQué practica
1Maximum GCD (1370A)★ (800)pensar el MCD, no calcularlo
2Almost Prime (26A)★★ (900)divisores primos con √n
3Modular Exponentiation (913A)★★ (900)potencias de 2 y %, con caso borde
4Sum of Digits (102B)★★ (1000)desarmar dígitos, número gigante como string
5⭐ T-primes (230B)★★★ (1300)criba + una observación bonita

Un ejemplo para pensar

En un reloj con posiciones de 0 a 9 estamos en el 2 y retrocedemos cinco pasos. La posición matemática es 7, pero en C++ (2 - 5) % 10 vale −3. ¿Cómo pueden describir el mismo desplazamiento?


← 09 - Recursión · Ruta de Aprendizaje · 11 - Colas de prioridad →