CP-UPV Bootcamp - Capítulo 6

Capítulo 6: Teoría de Números

Índice de contenidos

• 1. Introducción a la Teoría de Números en CP
• 2. Números Primos
• Ejemplo 1: El Sorteo de Bombillas de la Delegación
• 3. Factorización y Teorema Fundamental de la Aritmética
• Ejemplo 2: Los Divisores del Casillero de Diego Provencio
• 4. Máximo Común Divisor y Mínimo Común Múltiplo
• 5. El Algoritmo de Euclides
• 6. El Algoritmo Extendido de Euclides e Identidad de Bézout
• Ejemplo 3: El Inverso Perdido de la ETSINF
• 7. Congruencias y Aritmética Modular
• 8. Exponenciación Rápida
• 9. Inverso Modular y Combinatoria Modular
• Ejemplo 4: Las Combinaciones de Camisetas de CP-UPV
• 10. Congruencias Lineales
• 11. El Teorema del Resto Chino (CRT)
• Ejemplo 5: El Horario Imposible de los Becarios
• 12. Función Phi de Euler y Pequeño Teorema de Fermat
• 13. Números Perfectos, Abundantes y Deficientes
• Ejemplo 6: El Catálogo Numerológico de Diego Provencio
• Problemas de práctica

1. Introducción a la Teoría de Números en CP

La Teoría de Números es la rama de las matemáticas que estudia las propiedades de los números enteros: divisibilidad, primalidad, congruencias, y las relaciones estructurales entre ellos. Puede sonar a matemática "pura" alejada de la programación, pero en realidad es uno de los pilares más frecuentes en programación competitiva: desde calcular combinatoria modular en un problema de conteo, hasta detectar ciclos con congruencias, pasando por criptografía simplificada (RSA básico) o resolver sistemas de ecuaciones modulares.

Lo interesante de este bloque es que, a diferencia de otras estructuras de datos, aquí no se trata de contenedores, sino de algoritmos matemáticos con complejidades muy concretas que debemos saber reconocer: criba de primos en $O(N \log \log N)$, Euclides en $O(\log(\min(a,b)))$, exponenciación rápida en $O(\log N)$... Dominar estas piezas te permitirá resolver en milisegundos problemas que, atacados de forma ingenua (fuerza bruta), tardarían literalmente años en ejecutarse.

A lo largo de este capítulo trabajaremos con:

• Números primos, cribas y factorización.
• MCD, MCM y el algoritmo de Euclides (normal y extendido).
• Aritmética modular: congruencias, exponenciación rápida e inversos modulares.
• Sistemas de congruencias con el Teorema del Resto Chino.
• La función $\varphi$ de Euler y el Pequeño Teorema de Fermat.
• Clasificaciones curiosas de números: perfectos, abundantes y deficientes.

2. Números Primos

Un número primo es un entero $p > 1$ cuyos únicos divisores positivos son $1$ y él mismo. Los números primos son los "átomos" de la aritmética: todo entero mayor que 1 puede descomponerse de forma única como producto de primos (lo veremos formalmente en el Teorema Fundamental de la Aritmética).

Test de primalidad ingenuo vs. $O(\sqrt{N})$

Comprobar si $N$ es primo probando todos los divisores de $2$ a $N-1$ cuesta $O(N)$. Podemos mejorarlo drásticamente observando que si $N = a \times b$ con $a \le b$, entonces necesariamente $a \le \sqrt{N}$. Por tanto, basta con comprobar divisores hasta $\sqrt{N}$.

// Comprobación de primalidad en O(sqrt(N))
bool esPrimo(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

import math

def es_primo(n):
    if n < 2:
        return False
    for i in range(2, int(math.isqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

static boolean esPrimo(long n) {
    if (n < 2) return false;
    for (long i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

Criba de Eratóstenes: primos hasta $N$ en $O(N \log \log N)$

Cuando necesitamos saber qué números son primos dentro de un rango completo (por ejemplo, todos los primos hasta $10^7$), comprobar uno a uno con el test anterior sería demasiado lento ($O(N \sqrt{N})$). La Criba de Eratóstenes resuelve esto marcando de forma inteligente los múltiplos de cada primo encontrado.

Idea: partimos de un array booleano marcando todo como "posible primo". Recorremos de $2$ en adelante; si un número no ha sido marcado como compuesto, es primo, y marcamos como compuestos todos sus múltiplos. Gracias a la serie armónica de primos, el coste total amortizado es $O(N \log \log N)$, prácticamente lineal.

// Criba de Eratóstenes: es_primo[i] == true si i es primo
vector<bool> cribaEratostenes(int limite) {
    vector<bool> es_primo(limite + 1, true);
    es_primo[0] = es_primo[1] = false;

    for (int i = 2; (long long)i * i <= limite; i++) {
        if (es_primo[i]) {
            // Empezamos a tachar desde i*i (los menores ya se tacharon antes)
            for (int j = i * i; j <= limite; j += i) {
                es_primo[j] = false;
            }
        }
    }
    return es_primo;
}

def criba_eratostenes(limite):
    es_primo = [True] * (limite + 1)
    es_primo[0] = es_primo[1] = False

    i = 2
    while i * i <= limite:
        if es_primo[i]:
            # Tachamos desde i*i con paso i
            for j in range(i * i, limite + 1, i):
                es_primo[j] = False
        i += 1

    return es_primo

static boolean[] cribaEratostenes(int limite) {
    boolean[] esPrimo = new boolean[limite + 1];
    Arrays.fill(esPrimo, true);
    esPrimo[0] = esPrimo[1] = false;

    for (int i = 2; (long) i * i <= limite; i++) {
        if (esPrimo[i]) {
            for (long j = (long) i * i; j <= limite; j += i) {
                esPrimo[(int) j] = false;
            }
        }
    }
    return esPrimo;
}

Ejemplo 1: El Sorteo de Bombillas de la Delegación

La Delegación de Alumnos de la ETSINF ha instalado $N$ bombillas numeradas de $1$ a $N$ en el pasillo, todas apagadas. Se van a realizar $N$ pasadas: en la pasada $i$-ésima, se cambia de estado (se enciende si estaba apagada, se apaga si estaba encendida) cada bombilla cuyo número sea múltiplo de $i$. Al finalizar las $N$ pasadas, se te pide contar cuántas bombillas quedan encendidas.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n;
    if (!(cin >> n)) return 0;

    // Una bombilla k queda encendida <=> k es un cuadrado perfecto
    // (número impar de divisores). Contamos cuántos cuadrados perfectos hay en [1, n].
    long long encendidas = (long long) sqrtl((long double) n);

    // Ajuste de seguridad por posibles errores de precisión en sqrt
    while (encendidas * encendidas > n) encendidas--;
    while ((encendidas + 1) * (encendidas + 1) <= n) encendidas++;

    cout << encendidas << "\n";

    return 0;
}

import sys
import math

def resolver():
    n = int(sys.stdin.read().split()[0])

    # El número de cuadrados perfectos <= n es floor(sqrt(n))
    encendidas = math.isqrt(n)

    print(encendidas)

if __name__ == "__main__":
    resolver()

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader lector = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(lector.readLine().trim());

        long encendidas = (long) Math.sqrt((double) n);
        while (encendidas * encendidas > n) encendidas--;
        while ((encendidas + 1) * (encendidas + 1) <= n) encendidas++;

        System.out.println(encendidas);
    }
}

3. Factorización y Teorema Fundamental de la Aritmética

El Teorema Fundamental de la Aritmética establece que todo entero $N > 1$ se puede representar de forma única (salvo el orden de los factores) como un producto de números primos:

$$N = p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k}$$

Esta descomposición es extremadamente potente en programación competitiva porque, a partir de ella, podemos calcular directamente propiedades como el número de divisores de $N$ ($\prod (e_i + 1)$), la suma de divisores, si $N$ es un cuadrado perfecto (todos los $e_i$ pares), o el propio MCD/MCM entre dos números.

Factorizar un único número en $O(\sqrt{N})$

// Devuelve pares (primo, exponente) de la factorización de n
vector<pair<long long, int>> factorizar(long long n) {
    vector<pair<long long, int>> factores;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            int exponente = 0;
            while (n % p == 0) {
                n /= p;
                exponente++;
            }
            factores.push_back({p, exponente});
        }
    }
    // Si queda un resto > 1, es un primo mayor que sqrt(n original)
    if (n > 1) factores.push_back({n, 1});
    return factores;
}

def factorizar(n):
    factores = []
    p = 2
    while p * p <= n:
        if n % p == 0:
            exponente = 0
            while n % p == 0:
                n //= p
                exponente += 1
            factores.append((p, exponente))
        p += 1
    if n > 1:
        factores.append((n, 1))
    return factores

static List<long[]> factorizar(long n) {
    List<long[]> factores = new ArrayList<>();
    for (long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            int exponente = 0;
            while (n % p == 0) {
                n /= p;
                exponente++;
            }
            factores.add(new long[]{p, exponente});
        }
    }
    if (n > 1) factores.add(new long[]{n, 1});
    return factores;
}

Factorizar muchas consultas: Criba de Factor Primo Mínimo (SPF)

Si necesitamos factorizar muchos números dentro de un rango $[1, N]$, factorizar cada uno con el método anterior sería $O(Q \sqrt{N})$. En su lugar, precalculamos con una criba modificada el Smallest Prime Factor (SPF) de cada número, y luego factorizamos dividiendo repetidamente por su SPF en $O(\log N)$ por consulta.

// spf[i] = factor primo más pequeño de i
vector<int> cribaSPF(int limite) {
    vector<int> spf(limite + 1);
    for (int i = 2; i <= limite; i++) {
        if (spf[i] == 0) { // i es primo (no fue marcado por ningún menor)
            for (int j = i; j <= limite; j += i) {
                if (spf[j] == 0) spf[j] = i;
            }
        }
    }
    return spf;
}

// Factorización en O(log N) usando la tabla SPF precalculada
vector<pair<int, int>> factorizarConSPF(int n, const vector<int>& spf) {
    vector<pair<int, int>> factores;
    while (n > 1) {
        int p = spf[n];
        int exponente = 0;
        while (n % p == 0) { n /= p; exponente++; }
        factores.push_back({p, exponente});
    }
    return factores;
}

def criba_spf(limite):
    spf = [0] * (limite + 1)
    for i in range(2, limite + 1):
        if spf[i] == 0:  # i es primo
            for j in range(i, limite + 1, i):
                if spf[j] == 0:
                    spf[j] = i
    return spf


def factorizar_con_spf(n, spf):
    factores = []
    while n > 1:
        p = spf[n]
        exponente = 0
        while n % p == 0:
            n //= p
            exponente += 1
        factores.append((p, exponente))
    return factores

static int[] cribaSPF(int limite) {
    int[] spf = new int[limite + 1];
    for (int i = 2; i <= limite; i++) {
        if (spf[i] == 0) {
            for (int j = i; j <= limite; j += i) {
                if (spf[j] == 0) spf[j] = i;
            }
        }
    }
    return spf;
}

static List<int[]> factorizarConSPF(int n, int[] spf) {
    List<int[]> factores = new ArrayList<>();
    while (n > 1) {
        int p = spf[n];
        int exponente = 0;
        while (n % p == 0) { n /= p; exponente++; }
        factores.add(new int[]{p, exponente});
    }
    return factores;
}

Ejemplo 2: Los Divisores del Casillero de Diego Provencio

A Diego Provencio le han asignado un casillero en el laboratorio identificado con un número $N$. Como es curioso, quiere saber cuántos divisores positivos tiene $N$ (incluyendo el 1 y el propio $N$), pero se le van a hacer $Q$ preguntas de este tipo sobre distintos casilleros, así que necesita una solución eficiente. Para cada consulta con un valor $N$ ($1 \le N \le 10^6$), imprime la cantidad de divisores de $N$.

#include <bits/stdc++.h>
using namespace std;

const int LIMITE = 1000000;
vector<int> spf(LIMITE + 1, 0);

void precalcularSPF() {
    for (int i = 2; i <= LIMITE; i++) {
        if (spf[i] == 0) {
            for (int j = i; j <= LIMITE; j += i) {
                if (spf[j] == 0) spf[j] = i;
            }
        }
    }
}

int contarDivisores(int n) {
    long long total = 1;
    while (n > 1) {
        int p = spf[n];
        int exponente = 0;
        while (n % p == 0) { n /= p; exponente++; }
        total *= (exponente + 1);
    }
    return (int) total;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    precalcularSPF();

    int q;
    if (!(cin >> q)) return 0;

    while (q--) {
        int n;
        cin >> n;
        cout << contarDivisores(n) << "\n";
    }

    return 0;
}

import sys

LIMITE = 10**6

def precalcular_spf(limite):
    spf = [0] * (limite + 1)
    for i in range(2, limite + 1):
        if spf[i] == 0:
            for j in range(i, limite + 1, i):
                if spf[j] == 0:
                    spf[j] = i
    return spf


def contar_divisores(n, spf):
    total = 1
    while n > 1:
        p = spf[n]
        exponente = 0
        while n % p == 0:
            n //= p
            exponente += 1
        total *= (exponente + 1)
    return total


def resolver():
    entrada = sys.stdin.read().split()
    q = int(entrada[0])
    spf = precalcular_spf(LIMITE)

    salida = []
    for i in range(1, q + 1):
        n = int(entrada[i])
        salida.append(str(contar_divisores(n, spf)))

    print("\n".join(salida))

if __name__ == "__main__":
    resolver()

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    static final int LIMITE = 1_000_000;
    static int[] spf = new int[LIMITE + 1];

    static void precalcularSPF() {
        for (int i = 2; i <= LIMITE; i++) {
            if (spf[i] == 0) {
                for (int j = i; j <= LIMITE; j += i) {
                    if (spf[j] == 0) spf[j] = i;
                }
            }
        }
    }

    static long contarDivisores(int n) {
        long total = 1;
        while (n > 1) {
            int p = spf[n];
            int exponente = 0;
            while (n % p == 0) { n /= p; exponente++; }
            total *= (exponente + 1);
        }
        return total;
    }

    public static void main(String[] args) throws IOException {
        precalcularSPF();

        BufferedReader lector = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(lector.readLine().trim());
        PrintWriter escritor = new PrintWriter(System.out);

        for (int i = 0; i < q; i++) {
            int n = Integer.parseInt(lector.readLine().trim());
            escritor.println(contarDivisores(n));
        }

        escritor.flush();
    }
}

4. Máximo Común Divisor y Mínimo Común Múltiplo

El Máximo Común Divisor ($\gcd$) de dos enteros $a$ y $b$ es el mayor entero que divide a ambos simultáneamente. El Mínimo Común Múltiplo ($\text{lcm}$) es el menor entero positivo que es múltiplo de ambos. Ambos conceptos aparecen constantemente en problemas de fracciones, sincronización de ciclos (por ejemplo, "¿cada cuántos días coinciden dos eventos periódicos?") y simplificación de razones.

Existe una relación muy útil entre ambos que se deduce directamente del Teorema Fundamental de la Aritmética:

$$\text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$$

// std::gcd y std::lcm ya vienen incluidos desde C++17 en <numeric>
long long a = 24, b = 36;
long long mcd = gcd(a, b);       // 12
long long mcm = lcm(a, b);       // 72

// Implementación manual segura frente a overflow
long long lcmSeguro(long long a, long long b) {
    return (a / gcd(a, b)) * b;
}

import math

a, b = 24, 36
mcd = math.gcd(a, b)   # 12
mcm = math.lcm(a, b)   # 72 (disponible desde Python 3.9)

# Implementación manual si se necesitase
def lcm_manual(a, b):
    return a // math.gcd(a, b) * b

// Java no trae gcd/lcm built-in de forma directa (salvo BigInteger.gcd)
static long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b);
}

static long lcm(long a, long b) {
    return (a / gcd(a, b)) * b; // dividimos antes de multiplicar para evitar overflow
}

5. El Algoritmo de Euclides

El Algoritmo de Euclides calcula el $\gcd(a, b)$ sin necesidad de factorizar ninguno de los dos números, apoyándose en la siguiente propiedad:

$$\gcd(a, b) = \gcd(b, a \mod b)$$

La idea es que cualquier divisor común de $a$ y $b$ también lo es de $b$ y del resto $a \bmod b$. Repitiendo este proceso, el segundo argumento va decreciendo rápidamente hasta llegar a $0$, momento en el cual el primer argumento es la respuesta.

// Versión recursiva del algoritmo de Euclides
long long gcdEuclides(long long a, long long b) {
    if (b == 0) return a;
    return gcdEuclides(b, a % b);
}

// Versión iterativa (evita el overhead de la recursión)
long long gcdIterativo(long long a, long long b) {
    while (b != 0) {
        long long resto = a % b;
        a = b;
        b = resto;
    }
    return a;
}

def gcd_euclides(a, b):
    if b == 0:
        return a
    return gcd_euclides(b, a % b)


def gcd_iterativo(a, b):
    while b != 0:
        a, b = b, a % b
    return a

static long gcdEuclides(long a, long b) {
    if (b == 0) return a;
    return gcdEuclides(b, a % b);
}

static long gcdIterativo(long a, long b) {
    while (b != 0) {
        long resto = a % b;
        a = b;
        b = resto;
    }
    return a;
}

6. El Algoritmo Extendido de Euclides e Identidad de Bézout

El Algoritmo Extendido de Euclides no solo calcula $\gcd(a, b)$, sino que además encuentra un par de enteros $x, y$ (posiblemente negativos) que satisfacen la Identidad de Bézout:

$$a \cdot x + b \cdot y = \gcd(a, b)$$

Esta identidad es la puerta de entrada a resolver congruencias lineales y calcular inversos modulares cuando el módulo no es primo (o cuando queremos evitar el pequeño teorema de Fermat).

// Calcula g = gcd(a, b) y coeficientes x, y tales que a*x + b*y = g
long long gcdExtendido(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long g = gcdExtendido(b, a % b, x1, y1);

    // Deshacemos la recursión aplicando la relación de recurrencia
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

def gcd_extendido(a, b):
    # Devuelve (g, x, y) tales que a*x + b*y = g = gcd(a, b)
    if b == 0:
        return a, 1, 0

    g, x1, y1 = gcd_extendido(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y

// Usamos un array de tamaño 2 como "salida por referencia" para x e y
static long gcdExtendido(long a, long b, long[] xy) {
    if (b == 0) {
        xy[0] = 1;
        xy[1] = 0;
        return a;
    }
    long[] xy1 = new long[2];
    long g = gcdExtendido(b, a % b, xy1);

    xy[0] = xy1[1];
    xy[1] = xy1[0] - (a / b) * xy1[1];
    return g;
}

Ejemplo 3: El Inverso Perdido de la ETSINF

El sistema de matrícula de la ETSINF cifra cada nota final $v$ (un entero entre $0$ y $M-1$) multiplicándola por una clave secreta $a$ módulo $M$, obteniendo $c = (a \cdot v) \bmod M$. Se sabe que $\gcd(a, M) = 1$. Dado $a$, $M$ y el valor cifrado $c$, recupera la nota original $v$.

#include <bits/stdc++.h>
using namespace std;

long long gcdExtendido(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = gcdExtendido(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long inversoModular(long long a, long long m) {
    long long x, y;
    gcdExtendido(a, m, x, y);
    // Normalizamos para que quede en el rango [0, m-1]
    return ((x % m) + m) % m;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long a, m, c;
    if (!(cin >> a >> m >> c)) return 0;

    long long a_inv = inversoModular(a, m);
    long long v = ( (__int128)c * a_inv ) % m; // __int128 evita overflow al multiplicar

    cout << v << "\n";

    return 0;
}

import sys

def gcd_extendido(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = gcd_extendido(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y


def inverso_modular(a, m):
    _, x, _ = gcd_extendido(a, m)
    return x % m


def resolver():
    a, m, c = map(int, sys.stdin.read().split())
    a_inv = inverso_modular(a, m)
    v = (c * a_inv) % m
    print(v)

if __name__ == "__main__":
    resolver()

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.math.BigInteger;

public class Main {
    static long gcdExtendido(long a, long b, long[] xy) {
        if (b == 0) { xy[0] = 1; xy[1] = 0; return a; }
        long[] xy1 = new long[2];
        long g = gcdExtendido(b, a % b, xy1);
        xy[0] = xy1[1];
        xy[1] = xy1[0] - (a / b) * xy1[1];
        return g;
    }

    static long inversoModular(long a, long m) {
        long[] xy = new long[2];
        gcdExtendido(a, m, xy);
        return ((xy[0] % m) + m) % m;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader lector = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(lector.readLine());

        long a = Long.parseLong(tokens.nextToken());
        long m = Long.parseLong(tokens.nextToken());
        long c = Long.parseLong(tokens.nextToken());

        long aInv = inversoModular(a, m);
        // Usamos BigInteger para evitar overflow en la multiplicación
        long v = BigInteger.valueOf(c).multiply(BigInteger.valueOf(aInv)).mod(BigInteger.valueOf(m)).longValue();

        System.out.println(v);
    }
}

7. Congruencias y Aritmética Modular

Decimos que $a$ es congruente con $b$ módulo $m$, y lo escribimos $a \equiv b \pmod{m}$, cuando $m$ divide exactamente a $a - b$ (es decir, $a$ y $b$ dejan el mismo resto al dividir entre $m$). La aritmética modular se comporta de forma muy natural respecto a la suma, resta y multiplicación:

• $(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$
• $(a - b) \bmod m = ((a \bmod m) - (b \bmod m) + m) \bmod m$ (sumamos $m$ para evitar restos negativos)
• $(a \times b) \bmod m = ((a \bmod m) \times (b \bmod m)) \bmod m$

La división es la única operación delicada: no podemos simplemente dividir módulo $m$, sino que necesitamos multiplicar por el inverso modular del divisor (lo veremos en la siguiente sección).

8. Exponenciación Rápida

Calcular $a^b$ multiplicando $a$ por sí mismo $b$ veces cuesta $O(b)$, algo inviable cuando $b$ puede ser del orden de $10^9$ o $10^{18}$. La Exponenciación Rápida (también llamada exponentiation by squaring) reduce esto a $O(\log b)$ aprovechando la representación binaria del exponente:

$$a^b = \begin{cases} 1 & \text{si } b = 0 \\ (a^{b/2})^2 & \text{si } b \text{ es par} \\ a \times (a^{(b-1)/2})^2 & \text{si } b \text{ es impar} \end{cases}$$

// Calcula (base^exponente) % mod en O(log exponente)
long long potenciaModular(long long base, long long exponente, long long mod) {
    base %= mod;
    long long resultado = 1;

    while (exponente > 0) {
        if (exponente & 1) { // Si el bit actual es 1
            resultado = (__int128)resultado * base % mod;
        }
        base = (__int128)base * base % mod;
        exponente >>= 1; // Avanzamos al siguiente bit
    }
    return resultado;
}

# Python trae exponenciación rápida modular integrada en pow()
resultado = pow(base, exponente, mod)  # O(log exponente), sin overflow

# Implementación manual equivalente, por si se necesita entender el proceso:
def potencia_modular(base, exponente, mod):
    base %= mod
    resultado = 1
    while exponente > 0:
        if exponente & 1:
            resultado = resultado * base % mod
        base = base * base % mod
        exponente >>= 1
    return resultado

static long potenciaModular(long base, long exponente, long mod) {
    base %= mod;
    long resultado = 1;

    while (exponente > 0) {
        if ((exponente & 1) == 1) {
            resultado = Math.multiplyHigh(resultado, base) == 0
                ? (resultado * base) % mod
                : (long) ((java.math.BigInteger.valueOf(resultado)
                    .multiply(java.math.BigInteger.valueOf(base))
                    .mod(java.math.BigInteger.valueOf(mod))).longValue());
            // En la práctica, para mod < 3*10^9, basta con:
            // resultado = (resultado * base) % mod;
        }
        base = (base * base) % mod;
        exponente >>= 1;
    }
    return resultado;
}

9. Inverso Modular y Combinatoria Modular

El inverso modular de $a$ respecto a $m$ es el número $a^{-1}$ tal que $a \times a^{-1} \equiv 1 \pmod{m}$, y solo existe si $\gcd(a, m) = 1$. Ya vimos cómo calcularlo con el algoritmo extendido de Euclides; cuando el módulo $m$ es primo (el caso más común en CP, con $m = 10^9+7$), existe un atajo mucho más simple gracias al Pequeño Teorema de Fermat:

$$a^{-1} \equiv a^{m-2} \pmod{m}$$

Esto convierte el cálculo del inverso en una simple exponenciación rápida, sin necesidad de implementar Euclides extendido.

Con el inverso modular podemos calcular combinatoria modular ($\binom{n}{k} \bmod p$), imprescindible en problemas de conteo:

$$\binom{n}{k} \equiv n! \times (k!)^{-1} \times ((n-k)!)^{-1} \pmod{p}$$

const long long MOD = 1e9 + 7;

// Requiere que MOD sea primo (Pequeño Teorema de Fermat)
long long inversoModularFermat(long long a) {
    return potenciaModular(a, MOD - 2, MOD);
}

// Precalculamos factoriales e inversos de factoriales hasta MAXN
const int MAXN = 1000006;
vector<long long> fact(MAXN), inv_fact(MAXN);

void precalcularFactoriales() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) fact[i] = fact[i - 1] * i % MOD;

    inv_fact[MAXN - 1] = inversoModularFermat(fact[MAXN - 1]);
    for (int i = MAXN - 2; i >= 0; i--) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    }
}

long long combinatoria(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

MOD = 10**9 + 7
MAXN = 1_000_006

def inverso_modular_fermat(a):
    return pow(a, MOD - 2, MOD)


# Precalculamos factoriales e inversos de factoriales hasta MAXN
fact = [1] * MAXN
for i in range(1, MAXN):
    fact[i] = fact[i - 1] * i % MOD

inv_fact = [1] * MAXN
inv_fact[MAXN - 1] = pow(fact[MAXN - 1], MOD - 2, MOD)
for i in range(MAXN - 2, -1, -1):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD


def combinatoria(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD

static final long MOD = 1_000_000_007L;
static final int MAXN = 1_000_006;
static long[] fact = new long[MAXN];
static long[] invFact = new long[MAXN];

static long inversoModularFermat(long a) {
    return potenciaModular(a, MOD - 2, MOD);
}

static void precalcularFactoriales() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) fact[i] = fact[i - 1] * i % MOD;

    invFact[MAXN - 1] = inversoModularFermat(fact[MAXN - 1]);
    for (int i = MAXN - 2; i >= 0; i--) {
        invFact[i] = invFact[i + 1] * (i + 1) % MOD;
    }
}

static long combinatoria(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}

Ejemplo 4: Las Combinaciones de Camisetas de CP-UPV

El equipo organizador de CP-UPV tiene $N$ diseños distintos de camiseta y quiere repartir un lote formando grupos regalo de exactamente $K$ camisetas distintas cada uno. Se te pide calcular de cuántas formas distintas se puede elegir un grupo regalo de $K$ camisetas entre las $N$ disponibles, dado que el resultado puede ser enorme: imprímelo módulo $10^9+7$. Se realizarán $Q$ consultas independientes, cada una con su propio par $(N, K)$.

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;
const int MAXN = 1000006;

vector<long long> fact(MAXN), inv_fact(MAXN);

long long potenciaModular(long long base, long long exponente, long long mod) {
    base %= mod;
    long long resultado = 1;
    while (exponente > 0) {
        if (exponente & 1) resultado = (__int128)resultado * base % mod;
        base = (__int128)base * base % mod;
        exponente >>= 1;
    }
    return resultado;
}

void precalcularFactoriales() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) fact[i] = fact[i - 1] * i % MOD;

    inv_fact[MAXN - 1] = potenciaModular(fact[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    }
}

long long combinatoria(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    precalcularFactoriales();

    int q;
    if (!(cin >> q)) return 0;

    while (q--) {
        int n, k;
        cin >> n >> k;
        cout << combinatoria(n, k) << "\n";
    }

    return 0;
}

import sys

MOD = 10**9 + 7
MAXN = 1_000_006

def resolver():
    entrada = sys.stdin.read().split()
    q = int(entrada[0])

    fact = [1] * MAXN
    for i in range(1, MAXN):
        fact[i] = fact[i - 1] * i % MOD

    inv_fact = [1] * MAXN
    inv_fact[MAXN - 1] = pow(fact[MAXN - 1], MOD - 2, MOD)
    for i in range(MAXN - 2, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

    def combinatoria(n, k):
        if k < 0 or k > n:
            return 0
        return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD

    salida = []
    idx = 1
    for _ in range(q):
        n = int(entrada[idx]); k = int(entrada[idx + 1])
        idx += 2
        salida.append(str(combinatoria(n, k)))

    print("\n".join(salida))

if __name__ == "__main__":
    resolver()

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    static final long MOD = 1_000_000_007L;
    static final int MAXN = 1_000_006;
    static long[] fact = new long[MAXN];
    static long[] invFact = new long[MAXN];

    static long potenciaModular(long base, long exponente, long mod) {
        base %= mod;
        long resultado = 1;
        while (exponente > 0) {
            if ((exponente & 1) == 1) resultado = (resultado * base) % mod;
            base = (base * base) % mod;
            exponente >>= 1;
        }
        return resultado;
    }

    static void precalcularFactoriales() {
        fact[0] = 1;
        for (int i = 1; i < MAXN; i++) fact[i] = fact[i - 1] * i % MOD;

        invFact[MAXN - 1] = potenciaModular(fact[MAXN - 1], MOD - 2, MOD);
        for (int i = MAXN - 2; i >= 0; i--) {
            invFact[i] = invFact[i + 1] * (i + 1) % MOD;
        }
    }

    static long combinatoria(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
    }

    public static void main(String[] args) throws IOException {
        precalcularFactoriales();

        BufferedReader lector = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(lector.readLine().trim());
        PrintWriter escritor = new PrintWriter(System.out);

        for (int i = 0; i < q; i++) {
            StringTokenizer tokens = new StringTokenizer(lector.readLine());
            int n = Integer.parseInt(tokens.nextToken());
            int k = Integer.parseInt(tokens.nextToken());
            escritor.println(combinatoria(n, k));
        }

        escritor.flush();
    }
}

10. Congruencias Lineales

Una congruencia lineal tiene la forma:

$$a \cdot x \equiv b \pmod{m}$$

y buscamos los valores de $x$ que la satisfacen. Sea $g = \gcd(a, m)$. Esta ecuación tiene solución si y solo si $g$ divide a $b$. Cuando tiene solución, existen exactamente $g$ soluciones distintas módulo $m$, y se pueden obtener a partir de una solución particular usando el algoritmo extendido de Euclides sobre $a$ y $m$.

Procedimiento:

1. Calcula $g = \gcd(a, m)$ junto con $x_0, y_0$ tales que $a x_0 + m y_0 = g$ (Euclides extendido).
2. Si $b \bmod g \ne 0$, no hay solución.
3. Si hay solución, una solución particular es $x_p = x_0 \cdot (b / g) \bmod m$.
4. Todas las soluciones módulo $m$ son $x_p + k \cdot (m / g)$ para $k = 0, 1, \dots, g-1$.

// Resuelve a*x = b (mod m). Devuelve false si no hay solución.
// Si hay solución, x0 es una solución particular y periodo = m / gcd(a, m)
bool congruenciaLineal(long long a, long long b, long long m, long long &x0, long long &periodo) {
    long long p, q;
    long long g = gcdExtendido(a, m, p, q);

    if (b % g != 0) return false; // No hay solución

    periodo = m / g;
    x0 = ( (__int128)p * (b / g) % periodo + periodo ) % periodo;
    return true;
}

def congruencia_lineal(a, b, m):
    # Resuelve a*x = b (mod m). Devuelve None si no hay solución,
    # o (x0, periodo) donde las soluciones son x0 + k*periodo, k = 0..g-1
    g, p, _ = gcd_extendido(a, m)

    if b % g != 0:
        return None

    periodo = m // g
    x0 = (p * (b // g)) % periodo
    return x0, periodo

// Resuelve a*x = b (mod m). Devuelve null si no hay solución.
// result[0] = solución particular x0, result[1] = periodo
static long[] congruenciaLineal(long a, long b, long m) {
    long[] xy = new long[2];
    long g = gcdExtendido(a, m, xy);

    if (b % g != 0) return null;

    long periodo = m / g;
    long x0 = ((xy[0] * (b / g)) % periodo + periodo) % periodo;
    return new long[]{x0, periodo};
}

11. El Teorema del Resto Chino (CRT)

El Teorema del Resto Chino (Chinese Remainder Theorem) responde a una pregunta muy natural: si conocemos el resto de un número $x$ al dividirlo entre varios módulos distintos, ¿podemos reconstruir $x$? Formalmente, dado el sistema:

$$x \equiv r_1 \pmod{m_1}, \quad x \equiv r_2 \pmod{m_2}, \quad \dots, \quad x \equiv r_k \pmod{m_k}$$

si los módulos $m_1, \dots, m_k$ son coprimos entre sí, entonces existe una única solución módulo $M = m_1 \times m_2 \times \dots \times m_k$.

Este teorema aparece de forma recurrente en problemas de "eventos periódicos" (dos sucesos que se repiten con distinta periodicidad, ¿cuándo vuelven a coincidir?) y en criptografía. Podemos combinar las congruencias de dos en dos, generalizando incluso a módulos no necesariamente coprimos (comprobando compatibilidad vía $\gcd$).

// Combina x = r1 (mod m1) y x = r2 (mod m2) en una única congruencia
// x = r (mod lcm(m1, m2)). Devuelve false si el sistema es incompatible.
bool combinarCRT(long long r1, long long m1, long long r2, long long m2,
                  long long &r, long long &m) {
    long long p, q;
    long long g = gcdExtendido(m1, m2, p, q);

    if ((r2 - r1) % g != 0) return false; // Sistema incompatible

    long long lcm = m1 / g * m2;

    // Construimos la solución combinada módulo lcm(m1, m2)
    __int128 diff = (r2 - r1) / g;
    __int128 x = ( (__int128)r1 + (__int128)m1 * ( ( (__int128)p * diff ) % (lcm / m1) ) );
    x %= lcm;
    if (x < 0) x += lcm;

    r = (long long) x;
    m = lcm;
    return true;
}

def combinar_crt(r1, m1, r2, m2):
    # Combina x = r1 (mod m1) y x = r2 (mod m2)
    # Devuelve (r, m) con x = r (mod m), m = lcm(m1, m2), o None si es incompatible
    g, p, _ = gcd_extendido(m1, m2)

    if (r2 - r1) % g != 0:
        return None

    lcm = m1 // g * m2
    diff = (r2 - r1) // g
    x = (r1 + m1 * ((p * diff) % (lcm // m1))) % lcm

    return x, lcm


def resolver_sistema_crt(restos, modulos):
    # Combina una lista de congruencias progresivamente
    r, m = restos[0], modulos[0]
    for i in range(1, len(restos)):
        resultado = combinar_crt(r, m, restos[i], modulos[i])
        if resultado is None:
            return None
        r, m = resultado
    return r, m

import java.math.BigInteger;

// Combina x = r1 (mod m1) y x = r2 (mod m2) usando BigInteger para evitar overflow
static long[] combinarCRT(long r1, long m1, long r2, long m2) {
    long[] xy = new long[2];
    long g = gcdExtendido(m1, m2, xy);

    if ((r2 - r1) % g != 0) return null; // Incompatible

    BigInteger M1 = BigInteger.valueOf(m1);
    BigInteger M2 = BigInteger.valueOf(m2);
    BigInteger G = BigInteger.valueOf(g);
    BigInteger LCM = M1.divide(G).multiply(M2);

    BigInteger P = BigInteger.valueOf(xy[0]);
    BigInteger DIFF = BigInteger.valueOf((r2 - r1) / g);

    BigInteger x = BigInteger.valueOf(r1)
            .add(M1.multiply(P.multiply(DIFF).mod(LCM.divide(M1))))
            .mod(LCM);

    return new long[]{x.longValue(), LCM.longValue()};
}

Ejemplo 5: El Horario Imposible de los Becarios

En CP-UPV hay $K$ becarios de laboratorio. El becario $i$-ésimo tiene turno cada $m_i$ días exactos, y su próximo turno cae dentro de $r_i$ días a partir de hoy (es decir, sus turnos ocurren en los días $x$ tales que $x \equiv r_i \pmod{m_i}$, contando hoy como el día $0$). Se garantiza que todos los $m_i$ son coprimos entre sí. Calcula el primer día $x \ge 0$ en el que todos los becarios coinciden de turno a la vez, módulo $10^9+7$ (ya que el día exacto puede ser astronómicamente grande).

#include <bits/stdc++.h>
using namespace std;

const long long MOD_SALIDA = 1e9 + 7;

long long gcdExtendido(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = gcdExtendido(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// Combina x = r1 (mod m1) y x = r2 (mod m2) (módulos coprimos)
pair<long long, long long> combinarCRT(long long r1, long long m1, long long r2, long long m2) {
    long long p, q;
    gcdExtendido(m1, m2, p, q); // gcd(m1, m2) == 1 garantizado por el enunciado
    long long lcm = m1 * m2;

    __int128 diff = r2 - r1;
    __int128 x = (__int128)r1 + (__int128)m1 * ( ( (__int128)p * diff ) % m2 );
    x %= lcm;
    if (x < 0) x += lcm;

    return { (long long)(x % MOD_SALIDA), lcm }; // el resto módulo 1e9+7 ya para la salida final
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int k;
    if (!(cin >> k)) return 0;

    vector<long long> r(k), m(k);
    for (int i = 0; i < k; i++) cin >> r[i] >> m[i];

    // Para no perder precisión al combinar, mantenemos también el resto SIN reducir mod 1e9+7
    // usando aritmética exacta hasta el final gracias a __int128.
    __int128 r_acum = r[0] % m[0];
    __int128 m_acum = m[0];

    for (int i = 1; i < k; i++) {
        long long p, q;
        gcdExtendido((long long)(m_acum % m[i] == 0 ? m[i] : m_acum), m[i], p, q); // gcd(m_acum, m[i]) = 1
        // Recalculamos con precisión completa usando la fórmula estándar de CRT
        __int128 diff = r[i] - (long long)(r_acum % m[i]);
        __int128 lcm = m_acum * m[i];
        __int128 x = r_acum + m_acum * ( ( (__int128)p * diff ) % m[i] );
        x %= lcm;
        if (x < 0) x += lcm;

        r_acum = x;
        m_acum = lcm;
    }

    long long respuesta = (long long)(r_acum % MOD_SALIDA);
    cout << respuesta << "\n";

    return 0;
}

import sys

MOD_SALIDA = 10**9 + 7

def gcd_extendido(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = gcd_extendido(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y


def combinar_crt(r1, m1, r2, m2):
    g, p, _ = gcd_extendido(m1, m2)  # g == 1, módulos coprimos garantizados
    lcm = m1 * m2
    diff = r2 - r1
    x = (r1 + m1 * ((p * diff) % m2)) % lcm
    return x, lcm


def resolver():
    entrada = sys.stdin.read().split()
    k = int(entrada[0])

    r = [0] * k
    m = [0] * k
    idx = 1
    for i in range(k):
        r[i] = int(entrada[idx]); m[i] = int(entrada[idx + 1])
        idx += 2

    r_acum, m_acum = r[0] % m[0], m[0]
    for i in range(1, k):
        # Python maneja enteros de precisión arbitraria de forma nativa,
        # así que no hay riesgo de overflow al combinar las congruencias.
        r_acum, m_acum = combinar_crt(r_acum, m_acum, r[i], m[i])

    print(r_acum % MOD_SALIDA)

if __name__ == "__main__":
    resolver()

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) throws IOException {
        BigInteger MOD_SALIDA = BigInteger.valueOf(1_000_000_007L);

        BufferedReader lector = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(lector.readLine().trim());

        BigInteger[] r = new BigInteger[k];
        BigInteger[] m = new BigInteger[k];

        for (int i = 0; i < k; i++) {
            StringTokenizer tokens = new StringTokenizer(lector.readLine());
            r[i] = new BigInteger(tokens.nextToken());
            m[i] = new BigInteger(tokens.nextToken());
        }

        // BigInteger evita cualquier problema de overflow al combinar congruencias
        BigInteger rAcum = r[0].mod(m[0]);
        BigInteger mAcum = m[0];

        for (int i = 1; i < k; i++) {
            BigInteger[] egcd = gcdExtendidoBig(mAcum, m[i]);
            BigInteger p = egcd[1];
            BigInteger lcm = mAcum.multiply(m[i]);
            BigInteger diff = r[i].subtract(rAcum);

            BigInteger x = rAcum.add(mAcum.multiply(p.multiply(diff).mod(m[i]))).mod(lcm);
            if (x.signum() < 0) x = x.add(lcm);

            rAcum = x;
            mAcum = lcm;
        }

        System.out.println(rAcum.mod(MOD_SALIDA));
    }

    // Devuelve {gcd, x, y} tal que a*x + b*y = gcd usando BigInteger
    static BigInteger[] gcdExtendidoBig(BigInteger a, BigInteger b) {
        if (b.equals(BigInteger.ZERO)) {
            return new BigInteger[]{a, BigInteger.ONE, BigInteger.ZERO};
        }
        BigInteger[] resultado = gcdExtendidoBig(b, a.mod(b));
        BigInteger g = resultado[0];
        BigInteger x1 = resultado[1];
        BigInteger y1 = resultado[2];

        BigInteger x = y1;
        BigInteger y = x1.subtract(a.divide(b).multiply(y1));
        return new BigInteger[]{g, x, y};
    }
}

12. Función Phi de Euler y Pequeño Teorema de Fermat

La función $\varphi$ de Euler (o totient), $\varphi(n)$, cuenta cuántos enteros en el rango $[1, n]$ son coprimos con $n$ (es decir, tienen $\gcd$ igual a $1$ con $n$). A partir de la factorización $n = p_1^{e_1} \cdots p_k^{e_k}$, se calcula con la fórmula:

$$\varphi(n) = n \times \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)$$

Esta función es la base del Teorema de Euler, una generalización del Pequeño Teorema de Fermat que funciona para cualquier módulo $m$ (no solo primos), siempre que $\gcd(a, m) = 1$:

$$a^{\varphi(m)} \equiv 1 \pmod{m}$$

El caso particular en que $m = p$ es primo da el Pequeño Teorema de Fermat ($\varphi(p) = p - 1$):

$$a^{p-1} \equiv 1 \pmod{p} \quad \Longrightarrow \quad a^{-1} \equiv a^{p-2} \pmod{p}$$

// Calcula phi(n) factorizando n en O(sqrt(n))
long long phiDeUnNumero(long long n) {
    long long resultado = n;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            resultado -= resultado / p; // resultado *= (1 - 1/p)
        }
    }
    if (n > 1) resultado -= resultado / n; // queda un primo grande
    return resultado;
}

// Criba de phi para TODOS los valores hasta 'limite' en O(N log log N)
vector<int> cribaPhi(int limite) {
    vector<int> phi(limite + 1);
    iota(phi.begin(), phi.end(), 0); // phi[i] = i inicialmente

    for (int p = 2; p <= limite; p++) {
        if (phi[p] == p) { // p es primo (no fue modificado todavía)
            for (int multiplo = p; multiplo <= limite; multiplo += p) {
                phi[multiplo] -= phi[multiplo] / p;
            }
        }
    }
    return phi;
}

def phi_de_un_numero(n):
    resultado = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            resultado -= resultado // p
        p += 1
    if n > 1:
        resultado -= resultado // n
    return resultado


def criba_phi(limite):
    phi = list(range(limite + 1))
    for p in range(2, limite + 1):
        if phi[p] == p:  # p es primo
            for multiplo in range(p, limite + 1, p):
                phi[multiplo] -= phi[multiplo] // p
    return phi

static long phiDeUnNumero(long n) {
    long resultado = n;
    for (long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            resultado -= resultado / p;
        }
    }
    if (n > 1) resultado -= resultado / n;
    return resultado;
}

static int[] cribaPhi(int limite) {
    int[] phi = new int[limite + 1];
    for (int i = 0; i <= limite; i++) phi[i] = i;

    for (int p = 2; p <= limite; p++) {
        if (phi[p] == p) {
            for (int multiplo = p; multiplo <= limite; multiplo += p) {
                phi[multiplo] -= phi[multiplo] / p;
            }
        }
    }
    return phi;
}

13. Números Perfectos, Abundantes y Deficientes

Clasificamos un número entero positivo $n$ según cómo se compara con la suma de sus divisores propios (todos los divisores de $n$ excepto el propio $n$), que denotamos $\sigma^*(n)$:

• Número Perfecto: $\sigma^*(n) = n$. Ejemplo clásico: $6 = 1 + 2 + 3$, o $28 = 1 + 2 + 4 + 7 + 14$.
• Número Abundante: $\sigma^*(n) > n$. Ejemplo: $12$, cuyos divisores propios suman $1+2+3+4+6=16 > 12$.
• Número Deficiente: $\sigma^*(n) < n$. Ejemplo: cualquier número primo $p$, ya que $\sigma^*(p) = 1 < p$.

Aunque parezcan curiosidades recreativas, estos conceptos aparecen en problemas de CP como excusa para practicar el cálculo eficiente de la suma de divisores, ya sea de un número aislado ($O(\sqrt{N})$) o de todo un rango con una criba tipo "suma de divisores" en $O(N \log N)$.

// Suma de divisores propios de n en O(sqrt(n))
long long sumaDivisoresPropios(long long n) {
    if (n == 1) return 0;
    long long suma = 1; // el 1 siempre es divisor propio (salvo de sí mismo)
    for (long long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            suma += d;
            if (d != n / d) suma += n / d; // evitamos contar dos veces la raíz cuadrada exacta
        }
    }
    return suma;
}

enum TipoNumero { PERFECTO, ABUNDANTE, DEFICIENTE };

TipoNumero clasificar(long long n) {
    long long suma = sumaDivisoresPropios(n);
    if (suma == n) return PERFECTO;
    if (suma > n) return ABUNDANTE;
    return DEFICIENTE;
}

// Suma de divisores propios para TODOS los números hasta 'limite' en O(N log N)
vector<long long> cribaSumaDivisoresPropios(int limite) {
    vector<long long> suma(limite + 1, 0);
    for (int d = 1; d <= limite; d++) {
        for (int multiplo = 2 * d; multiplo <= limite; multiplo += d) {
            suma[multiplo] += d; // d es divisor propio de todos sus múltiplos (salvo de sí mismo)
        }
    }
    return suma;
}

import math

def suma_divisores_propios(n):
    if n == 1:
        return 0
    suma = 1
    for d in range(2, math.isqrt(n) + 1):
        if n % d == 0:
            suma += d
            if d != n // d:
                suma += n // d
    return suma


def clasificar(n):
    suma = suma_divisores_propios(n)
    if suma == n:
        return "PERFECTO"
    elif suma > n:
        return "ABUNDANTE"
    else:
        return "DEFICIENTE"


def criba_suma_divisores_propios(limite):
    suma = [0] * (limite + 1)
    for d in range(1, limite + 1):
        for multiplo in range(2 * d, limite + 1, d):
            suma[multiplo] += d
    return suma

static long sumaDivisoresPropios(long n) {
    if (n == 1) return 0;
    long suma = 1;
    for (long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            suma += d;
            if (d != n / d) suma += n / d;
        }
    }
    return suma;
}

static String clasificar(long n) {
    long suma = sumaDivisoresPropios(n);
    if (suma == n) return "PERFECTO";
    if (suma > n) return "ABUNDANTE";
    return "DEFICIENTE";
}

static long[] cribaSumaDivisoresPropios(int limite) {
    long[] suma = new long[limite + 1];
    for (int d = 1; d <= limite; d++) {
        for (int multiplo = 2 * d; multiplo <= limite; multiplo += d) {
            suma[multiplo] += d;
        }
    }
    return suma;
}

Ejemplo 6: El Catálogo Numerológico de Diego Provencio

En sus ratos libres (los pocos que le quedan), Diego Provencio está catalogando los primeros $N$ números naturales según sean perfectos, abundantes o deficientes. Dado $N$ ($1 \le N \le 5 \times 10^5$), imprime tres números: la cantidad de números perfectos, la cantidad de números abundantes, y la cantidad de números deficientes en el rango $[1, N]$.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    // suma[i] = suma de divisores propios de i
    vector<long long> suma(n + 1, 0);
    for (int d = 1; d <= n; d++) {
        for (int multiplo = 2 * d; multiplo <= n; multiplo += d) {
            suma[multiplo] += d;
        }
    }

    long long perfectos = 0, abundantes = 0, deficientes = 0;
    for (int i = 1; i <= n; i++) {
        if (suma[i] == i) perfectos++;
        else if (suma[i] > i) abundantes++;
        else deficientes++;
    }

    cout << perfectos << " " << abundantes << " " << deficientes << "\n";

    return 0;
}

import sys

def resolver():
    n = int(sys.stdin.read().split()[0])

    suma = [0] * (n + 1)
    for d in range(1, n + 1):
        for multiplo in range(2 * d, n + 1, d):
            suma[multiplo] += d

    perfectos = abundantes = deficientes = 0
    for i in range(1, n + 1):
        if suma[i] == i:
            perfectos += 1
        elif suma[i] > i:
            abundantes += 1
        else:
            deficientes += 1

    print(perfectos, abundantes, deficientes)

if __name__ == "__main__":
    resolver()

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader lector = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(lector.readLine().trim());

        long[] suma = new long[n + 1];
        for (int d = 1; d <= n; d++) {
            for (int multiplo = 2 * d; multiplo <= n; multiplo += d) {
                suma[multiplo] += d;
            }
        }

        long perfectos = 0, abundantes = 0, deficientes = 0;
        for (int i = 1; i <= n; i++) {
            if (suma[i] == i) perfectos++;
            else if (suma[i] > i) abundantes++;
            else deficientes++;
        }

        System.out.println(perfectos + " " + abundantes + " " + deficientes);
    }
}

Problemas de práctica

Aplica las estructuras y técnicas aprendidas completando la serie de ejercicios asignados en el concurso activo de nuestro bootcamp en Codeforces.