Primalidad por división
Se verifica si un número tiene algún divisor propio probando únicamente hasta su raíz cuadrada.
bool esPrimo(int n) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int d = 3; d <= n / d; d += 2)
if (n % d == 0)
return false;
return true;
}
Factorización por división
void factorizar(int n) {
for (int d = 2; d <= n / d; ++d) {
if (n % d == 0) {
int e = 0;
while (n % d == 0) {
n /= d;
++e;
}
cout << d << ' ' << e << '\n';
}
}
if (n > 1) cout << n << ' ' << 1 << '\n';
}
Criba lineal para primos
vector<int> primos;
vector<char> compuesto;
void cribaLineal(int n) {
compuesto.assign(n + 1, false);
primos.clear();
for (int i = 2; i <= n; ++i) {
if (!compuesto[i]) primos.push_back(i);
for (size_t j = 0; j < primos.size(); ++j) {
long long v = 1LL * primos[j] * i;
if (v > n) break;
compuesto[v] = true;
if (i % primos[j] == 0) break;
}
}
}
Obtener todos los divisores
vector<int> obtenerDivisores(int n) {
vector<int> r;
for (int d = 1; d <= n / d; ++d) {
if (n % d == 0) {
r.push_back(d);
if (d != n / d) r.push_back(n / d);
}
}
sort(r.begin(), r.end());
return r;
}
Cantidad y suma de divisores
Si N = p<sub>1</sub><sup>c<sub>1</sub></sup> · p<sub>2</sub><sup>c<sub>2</sub></sup> ··· p<sub>k</sub><sup>c<sub>k</sub></sup>, entonces:
- Cantidad de divisores:
(c<sub>1</sub> + 1)(c<sub>2</sub> + 1)...(c<sub>k</sub> + 1) - Suma de divisores:
∏<sub>i</sub> (p<sub>i</sub><sup>0</sup> + p<sub>i</sub><sup>1</sup> + ... + p<sub>i</sub><sup>c<sub>i</sub></sup>)
Máximo común divisor
int mcd(int a, int b) {
while (b) {
int r = a % b;
a = b;
b = r;
}
return a;
}
Función totiente de Euler
int totiente(int n) {
int res = n;
for (int d = 2; d <= n / d; ++d)
if (n % d == 0) {
res = res / d * (d - 1);
while (n % d == 0) n /= d;
}
if (n > 1) res = res / n * (n - 1);
return res;
}
Criba lineal para la función totiente
vector<int> primos;
vector<char> compuesto;
vector<int> phi;
void cribaTotiente(int n) {
phi.assign(n + 1, 0);
compuesto.assign(n + 1, false);
primos.clear();
phi[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!compuesto[i]) {
primos.push_back(i);
phi[i] = i - 1;
}
for (size_t j = 0; j < primos.size(); ++j) {
long long v = 1LL * primos[j] * i;
if (v > n) break;
compuesto[v] = true;
if (i % primos[j] == 0) {
phi[v] = phi[i] * primos[j];
break;
}
phi[v] = phi[i] * (primos[j] - 1);
}
}
}
Exponenciación rápida
long long pot_mod(long long base, long long exp, long long mod) {
long long res = 1 % mod;
base %= mod;
while (exp > 0) {
if (exp & 1) res = res * base % mod;
base = base * base % mod;
exp >>= 1;
}
return res;
}
Algoritmo extendido de Euclides
int egcd(int a, int b, int &x, int &y) {
int x0 = 1, y0 = 0, x1 = 0, y1 = 1;
while (b != 0) {
int q = a / b;
int r = a % b;
int t;
a = b; b = r;
t = x0; x0 = x1; x1 = t - q * x1;
t = y0; y0 = y1; y1 = t - q * y1;
}
x = x0; y = y0;
return a;
}
Eliminación gaussiana
const double EPS = 1e-6;
int gauss(vector<vector<double> > &a) {
int n = a.size();
int r = 0;
for (int c = 0; c < n; ++c) {
if (r >= n) break;
int piv = r;
for (int i = r; i < n; ++i)
if (fabs(a[i][c]) > fabs(a[piv][c]))
piv = i;
if (fabs(a[piv][c]) < EPS) continue;
swap(a[piv], a[r]);
double div = a[r][c];
for (int j = c; j <= n; ++j) a[r][j] /= div;
for (int i = r + 1; i < n; ++i) if (fabs(a[i][c]) > EPS) {
double f = a[i][c];
for (int j = c; j <= n; ++j)
a[i][j] -= f * a[r][j];
}
++r;
}
for (int i = r; i < n; ++i)
if (fabs(a[i][n]) > EPS) return 2;
if (r < n) return 1;
for (int i = n - 1; i >= 0; --i)
for (int j = i + 1; j < n; ++j)
a[i][n] -= a[i][j] * a[j][n];
return 0;
}
Combinaciones por programación dinámica
const int MOD = 1e9 + 7;
const int LIM = 1000;
int C[LIM][LIM];
void initComb() {
for (int i = 0; i < LIM; ++i) {
C[i][0] = 1;
for (int j = 1; j <= i; ++j)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
}
}
Combinaciones con factoriales e inversos modulares
const int MOD = 1e9 + 7;
const int MAXN = 200000;
long long fact[MAXN], invFact[MAXN];
long long pot_mod(long long a, long long e) {
long long r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return r;
}
void initFactorial() {
fact[0] = invFact[0] = 1;
for (int i = 1; i < MAXN; ++i) {
fact[i] = fact[i - 1] * i % MOD;
invFact[i] = invFact[i - 1] * pot_mod(i, MOD - 2) % MOD;
}
}
long long comb(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}
Teorema de Lucas
long long binom_mod(long long a, long long b, int p) {
if (a < b) return 0;
long long num = 1, den = 1;
for (long long i = 1, j = a; i <= b; ++i, --j) {
num = num * j % p;
den = den * i % p;
}
return num * pot_mod(den, p - 2, p) % p;
}
long long lucas(long long a, long long b, int p) {
if (a < p && b < p) return binom_mod(a, b, p);
return lucas(a / p, b / p, p) * binom_mod(a % p, b % p, p) % p;
}
Valor exacto de combinaciones mediante factorización
vector<int> primos;
vector<char> compuesto;
vector<int> expPrimo;
void criba(int n) {
compuesto.assign(n + 1, false);
primos.clear();
for (int i = 2; i <= n; ++i) {
if (!compuesto[i]) primos.push_back(i);
for (size_t j = 0; j < primos.size(); ++j) {
long long v = 1LL * primos[j] * i;
if (v > n) break;
compuesto[v] = true;
if (i % primos[j] == 0) break;
}
}
}
int expEnFactorial(int n, int p) {
int res = 0;
while (n) {
n /= p;
res += n;
}
return res;
}
vector<int> multBig(vector<int> a, int b) {
vector<int> c;
long long carry = 0;
for (size_t i = 0; i < a.size(); ++i) {
carry += 1LL * a[i] * b;
c.push_back(int(carry % 10));
carry /= 10;
}
while (carry) {
c.push_back(int(carry % 10));
carry /= 10;
}
return c;
}
Para obtener C(a, b) exacto se procesa cada primo de la criba:
int a = ...; // valores del problema
int b = ...;
criba(a);
expPrimo.assign(primos.size(), 0);
for (size_t i = 0; i < primos.size(); ++i) {
int p = primos[i];
expPrimo[i] = expEnFactorial(a, p)
- expEnFactorial(b, p)
- expEnFactorial(a - b, p);
}
vector<int> res = {1};
for (size_t i = 0; i < primos.size(); ++i)
for (int j = 0; j < expPrimo[i]; ++j)
res = multBig(res, primos[i]);
Números de Catalan
El n-ésimo número de Catalan se calcula como:
Cat(n) = C(2n, n) / (n + 1)
Juego de Nim
En el Nim con varias pilas, el primer jugador tiene estrategia ganadora si y solo si el XOR de todos los tamaños de pila es distinto de cero:
A<sub>1</sub> ⊕ A<sub>2</sub> ⊕ ... ⊕ A<sub>n</sub> ≠ 0
Juegos combinatorios imparciales
Un juego es imparcial cuando:
- Participan dos jugadores por turnos.
- El conjunto de jugadas legales en cada estado no depende del jugador que tenga el turno.
- El jugador que no pueda mover pierde.
Juegos sobre grafos dirigidos
Cada estado se representa como un nodo; cada jugada legal es una arista dirigida hacia el siguiente estado. Todo juego imparcial puede modelarse así.
Operación mex
Para un conjunto S de enteros no negativos:
mex(S) = min { x ≥ 0 | x ∉ S }
Función SG
Para un nodo x con sucesores y<sub>1</sub>, y<sub>2</sub>, ..., y<sub>k</sub>:
SG(x) = mex({ SG(y<sub>1</sub>), SG(y<sub>2</sub>), ..., SG(y<sub>k</sub>) })
El valor del juego completo es SG(s), donde s es el nodo inicial.
Suma de juegos
Si un juego se descompone en subjuegos G<sub>1</sub>, G<sub>2</sub>, ..., G<sub>m</sub>, entonces:
SG(G) = SG(G<sub>1</sub>) ⊕ SG(G<sub>2</sub>) ⊕ ... ⊕ SG(G<sub>m</sub>)
Condición de victoria
Una posición es ganadora si SG(x) > 0 y perdedora si SG(x) == 0.