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.
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:
| paso | n | n % 10 (el dígito) | n / 10 (lo que queda) |
|---|---|---|---|
| 1 | 4025 | 5 | 402 |
| 2 | 402 | 2 | 40 |
| 3 | 40 | 0 | 4 |
| 4 | 4 | 4 | 0 ← 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 primero | 7 / 3 = 2 | -7 / 3 = −2 (no −3: trunca hacia el 0) |
| y después el resto | 7 − 3·2 = 1 | −7 − 3·(−2) = −1 |
| lo que casi siempre querías | 1 ✅ | 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:
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 necesitas | Qué usar | Costo |
|---|---|---|
| ¿este número es primo? (uno grande) | probar hasta la raíz | O(√n) |
| todos los primos hasta n (muchos chicos) | criba de Eratóstenes | O(n log log n) |
| en qué primos se descompone | Factorización | O(√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.
Si el diagrama no cabe, deslízalo horizontalmente.
En números, sigue la traza:
| paso | a | b | a % b (lo que sobra) |
|---|---|---|---|
| 1 | 48 | 18 | 48 % 18 = 12 |
| 2 | 18 | 12 | 18 % 12 = 6 |
| 3 | 12 | 6 | 12 % 6 = 0 |
| 4 | 6 | 0 | b 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ón | Producto que todavía representa la respuesta |
|---|---|
| inicio | 1 · 3¹³ |
| separar un factor porque 13 es impar | 3 · 3¹² |
| agrupar los doce factores por parejas | 3 · 9⁶ |
| agrupar de nuevo (6 es par) | 3 · 81³ |
| separar un 81 y agrupar los otros dos | 243 · 6561¹ |
| incorporar el último factor | 1594323 · 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) |
|---|---|---|---|
| 13 | sí → multiplica | 1 · 3 = 3 | 3² = 9 |
| 6 | no | 3 | 9² = 81 |
| 3 | sí → multiplica | 3 · 81 = 243 | 81² = 6561 → 561 |
| 1 | sí → multiplica | 243 · 561 = 136323 → 323 | — |
| 0 | fin | 323 |
Y acá está lo bonito:
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.
Idea para comprobar tu solución
El desplazamiento es −3, equivalente a 3 en ese reloj. Euclides recorre (30,18), (18,12), (12,6), (6,0); el MCM es 30/6·18=90. Para la potencia, 10=8+2 y 2¹⁰=1024, cuyo resto es 24. Son herramientas distintas.
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.
Una pista, si la necesitas
Busca el primer múltiplo positivo compartido. El resultado puede superar int.
Contrastar el razonamiento
Es el MCM:
(a / gcd(a,b)) * b, calculado en long long. Dividir primero evita un producto intermedio innecesario; con estas cotas el resultado no supera 10¹⁸.
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):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | El candado del basurero | Nacional 2019 | distancias en aritmética módulo 10 |
| 2 | Daniela y los múltiplos | Regional 2022 | múltiplos con saltos |
| 3 | Balancín | Nacional 2023 | el MCD resolviendo una ecuación |
| 4 | ⭐ Gollum vs Golomb | Nacional 2015 | recurrencias con n hasta 10¹⁰ y long long |
| 5 | ⭐⭐ Catalonia | Nacional 2020 | coordenadas en espiral hexagonal hasta 10¹⁸ |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Maximum GCD (1370A) | ★ (800) | pensar el MCD, no calcularlo |
| 2 | Almost Prime (26A) | ★★ (900) | divisores primos con √n |
| 3 | Modular Exponentiation (913A) | ★★ (900) | potencias de 2 y %, con caso borde |
| 4 | Sum 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?
Un resto negativo y su representante en el reloj
−3 y 7 difieren en una vuelta completa de 10, así que representan la misma posición módulo 10. La división entera de C++ trunca hacia cero y su resto puede ser negativo. Para obtener una posición entre 0 y 9,
((-3 % 10) + 10) % 10da 7. El último% 10también funciona cuando el resto original era cero: evita devolver 10.
← 09 - Recursión · Ruta de Aprendizaje · 11 - Colas de prioridad →