Tema 8
Manejo de números grandes y teoría de números
Patrón de examen
Si el problema pide 'mod 10⁹+7', usa aritmética modular. Para dividir con módulo, usa inverso modular. Solo implementa BigInteger si el problema pide el número completo sin módulo.
Explicación
El problema del overflow
| Tipo | Rango máximo |
|---|---|
int | ~2×10⁹ |
long long | ~9.2×10¹⁸ |
unsigned long long | ~1.8×10¹⁹ |
__int128 | ~1.7×10³⁸ (GCC) |
Cuando el resultado excede long long, necesitas aritmética modular o BigInteger manual.
Aritmética modular (la más común en olimpiadas)
Casi siempre el problema pide resultado mod 10⁹+7. Propiedades:
(a + b) % m = ((a%m) + (b%m)) % m(a * b) % m = ((a%m) * (b%m)) % m(a - b) % m = ((a%m) - (b%m) + m) % m— el+mevita negativos- División:
(a / b) % m = (a * b⁻¹) % mdonde b⁻¹ es el inverso modular
Inverso modular
Para dividir módulo un primo p: b⁻¹ = b^(p-2) mod p (Pequeño Teorema de Fermat).
Usa exponenciación rápida para calcularlo en O(log p).
Números grandes (BigInteger manual)
Cuando ni siquiera el módulo basta y necesitas el número completo:
- Almacenar dígitos en un
stringovector<int> - Implementar suma, resta y multiplicación dígito por dígito
Teoría de números esencial
MCD y MCM
MCD(a,b) = MCD(b, a%b)— EuclidesMCM(a,b) = a / MCD(a,b) * b— dividir primero evita overflow
Factorización en primos
Dividir por cada primo hasta √n. Útil para contar divisores o calcular funciones multiplicativas.