Divisores y Factorización

Divisores de un número

Un divisor de $n$ es un número que divide a $n$ sin dejar residuo.

Ejemplo

Los divisores de 12 son: 1, 2, 3, 4, 6, 12.

Encontrar todos los divisores

Método ingenuo: $O(n)$

vector<int> divisoresIngenuo(int n) {
    vector<int> divisores;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            divisores.push_back(i);
        }
    }
    return divisores;
}

Método optimizado: $O(\sqrt{n})$

Los divisores vienen en pares: si $d$ divide a $n$, entonces $n/d$ también divide a $n$. Solo necesitamos buscar hasta $\sqrt{n}$:

vector<int> divisores(int n) {
    vector<int> resultado;

    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            resultado.push_back(i);
            if (i != n / i) {
                resultado.push_back(n / i);
            }
        }
    }

    sort(resultado.begin(), resultado.end());
    return resultado;
}

Contar divisores

int contarDivisores(int n) {
    int cuenta = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            cuenta++;  // i es divisor
            if (i != n / i) {
                cuenta++;  // n/i también es divisor
            }
        }
    }
    return cuenta;
}

Suma de divisores

long long sumaDivisores(int n) {
    long long suma = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            suma += i;
            if (i != n / i) {
                suma += n / i;
            }
        }
    }
    return suma;
}

Factorización Prima

La factorización prima expresa un número como producto de sus factores primos.

Teorema Fundamental de la Aritmética

Todo entero mayor que 1 puede expresarse de forma única (salvo el orden) como producto de primos:

$n = p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_k^{a_k}$

Ejemplos

• $12 = 2^2 \cdot 3$
• $100 = 2^2 \cdot 5^2$
• $84 = 2^2 \cdot 3 \cdot 7$

Factorización por fuerza bruta: $O(\sqrt{n})$

vector<pair<int, int>> factorizar(int n) {
    vector<pair<int, int>> factores;  // {primo, exponente}

    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int exponente = 0;
            while (n % i == 0) {
                exponente++;
                n /= i;
            }
            factores.push_back({i, exponente});
        }
    }

    // Si queda un factor primo mayor que sqrt(n)
    if (n > 1) {
        factores.push_back({n, 1});
    }

    return factores;
}

Ejemplo de uso

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

int main() {
    int n = 84;

    auto factores = factorizar(n);

    cout << n << " = ";
    for (int i = 0; i < factores.size(); i++) {
        if (i > 0) cout << " × ";
        cout << factores[i].first;
        if (factores[i].second > 1) {
            cout << "^" << factores[i].second;
        }
    }
    cout << endl;
    // Salida: 84 = 2^2 × 3 × 7

    return 0;
}

Factorización con Criba (SPF)

Cuando necesitamos factorizar muchos números, podemos precalcular el Smallest Prime Factor (SPF) de cada número:

const int MAXN = 1e7;
int spf[MAXN + 1];  // Smallest Prime Factor

void calcularSPF() {
    for (int i = 0; i <= MAXN; i++) {
        spf[i] = i;  // Inicialmente, cada número es su propio SPF
    }

    for (int i = 2; i * i <= MAXN; i++) {
        if (spf[i] == i) {  // i es primo
            for (int j = i * i; j <= MAXN; j += i) {
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }
}

vector<pair<int, int>> factorizarConSPF(int n) {
    vector<pair<int, int>> factores;

    while (n > 1) {
        int primo = spf[n];
        int exponente = 0;

        while (n % primo == 0) {
            exponente++;
            n /= primo;
        }

        factores.push_back({primo, exponente});
    }

    return factores;
}

Complejidad:

• Precálculo: $O(n \log \log n)$
• Factorización: $O(\log n)$

Fórmulas útiles con factorización

Si $n = p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_k^{a_k}$:

Número de divisores

$\tau(n) = (a_1 + 1)(a_2 + 1)...(a_k + 1)$

int numeroDivisores(int n) {
    auto factores = factorizar(n);
    int resultado = 1;
    for (auto& [primo, exp] : factores) {
        resultado *= (exp + 1);
    }
    return resultado;
}

Suma de divisores

$\sigma(n) = \frac{p_1^{a_1+1} - 1}{p_1 - 1} \cdot \frac{p_2^{a_2+1} - 1}{p_2 - 1} \cdot ... \cdot \frac{p_k^{a_k+1} - 1}{p_k - 1}$

long long sumaDivisoresFormula(int n) {
    auto factores = factorizar(n);
    long long resultado = 1;

    for (auto& [primo, exp] : factores) {
        long long suma = 0;
        long long potencia = 1;
        for (int i = 0; i <= exp; i++) {
            suma += potencia;
            potencia *= primo;
        }
        resultado *= suma;
    }

    return resultado;
}

Función Phi de Euler

$\phi(n)$ cuenta cuántos números del 1 al $n$ son coprimos con $n$:

$\phi(n) = n \cdot \prod_{p | n} \left(1 - \frac{1}{p}\right)$

int phi(int n) {
    int resultado = n;

    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
            }
            resultado -= resultado / i;
        }
    }

    if (n > 1) {
        resultado -= resultado / n;
    }

    return resultado;
}

Precálculo de cantidad de divisores

Para contar divisores de números del 1 al $n$:

const int MAXN = 1e7;
int numDivisores[MAXN + 1];

void precalcularDivisores() {
    for (int i = 1; i <= MAXN; i++) {
        for (int j = i; j <= MAXN; j += i) {
            numDivisores[j]++;
        }
    }
}

Complejidad: $O(n \log n)$

Problemas de práctica

Problema 1: Divisores en rango

Cuenta cuántos números en $[L, R]$ tienen exactamente $k$ divisores:

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

int contarDivisores(int n) {
    int cuenta = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            cuenta++;
            if (i != n / i) cuenta++;
        }
    }
    return cuenta;
}

int main() {
    int L, R, k;
    cin >> L >> R >> k;

    int respuesta = 0;
    for (int i = L; i <= R; i++) {
        if (contarDivisores(i) == k) {
            respuesta++;
        }
    }

    cout << respuesta << endl;
    return 0;
}

Problema 2: Máximo divisor común con factorización

Calcular GCD usando factorización:

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

map<int, int> factorizar(int n) {
    map<int, int> factores;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            factores[i]++;
            n /= i;
        }
    }
    if (n > 1) factores[n]++;
    return factores;
}

int main() {
    int a, b;
    cin >> a >> b;

    auto fa = factorizar(a);
    auto fb = factorizar(b);

    long long gcd = 1;
    for (auto& [primo, exp] : fa) {
        if (fb.count(primo)) {
            int minExp = min(exp, fb[primo]);
            for (int i = 0; i < minExp; i++) {
                gcd *= primo;
            }
        }
    }

    cout << "GCD(" << a << ", " << b << ") = " << gcd << endl;
    return 0;
}

Problema 3: Número con más divisores

Encuentra el número más pequeño hasta $n$ con la mayor cantidad de divisores:

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

int contarDivisores(int n) {
    int cuenta = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            cuenta++;
            if (i != n / i) cuenta++;
        }
    }
    return cuenta;
}

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

    int maxDivisores = 0;
    int mejorNumero = 1;

    for (int i = 1; i <= n; i++) {
        int div = contarDivisores(i);
        if (div > maxDivisores) {
            maxDivisores = div;
            mejorNumero = i;
        }
    }

    cout << "Número: " << mejorNumero << endl;
    cout << "Divisores: " << maxDivisores << endl;

    return 0;
}

Problema 4: Producto de divisores

El producto de todos los divisores de $n$ es $n^{\tau(n)/2}$:

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

const long long MOD = 1e9 + 7;

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

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

    // Contar divisores
    long long tau = 0;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            tau++;
            if (i != n / i) tau++;
        }
    }

    // Producto = n^(tau/2)
    // Si tau es par: n^(tau/2)
    // Si tau es impar: sqrt(n)^tau = n^(tau/2) (n es cuadrado perfecto)

    long long producto;
    if (tau % 2 == 0) {
        producto = potencia(n % MOD, tau / 2, MOD);
    } else {
        // tau es impar, n es cuadrado perfecto
        long long raiz = sqrt(n);
        producto = potencia(raiz % MOD, tau, MOD);
    }

    cout << producto << endl;
    return 0;
}

Resumen

Ejercicios recomendados

1. CSES - Counting Divisors
2. CSES - Common Divisors
3. Codeforces - Divisibility by 2^n
4. AtCoder - Factorization