Divisibilidad

Si nunca se ha encontrado teoría de números, AoPS es un buen lugar para empezar.

Recursos

Factorización prima

Un entero positivo $a$ se llama divisor o factor de un entero no negativo $b$ si $b$ es divisible por $a$, lo que significa que existe algún entero $k$ tal que $b = ka$. Un entero $n > 1$ es primo si sus únicos divisores son $1$ y $n$. Los enteros mayores que $1$ que no son primos son compuestos.

Todo entero positivo tiene una factorización prima única: una forma de descomponerlo en un producto de primos, como sigue:

donde los $p_i$ son primos distintos y los $a_i$ son enteros positivos.

Ahora discutiremos cómo hallar la factorización prima de cualquier entero positivo.

vector<int> factor(int n) {
	vector<int> ret;
	for (int i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ret.push_back(i);
			n /= i;
		}
	}
	if (n > 1) { ret.push_back(n); }
	return ret;
}

List<Integer> factor(int n) {
	List<Integer> factors = new ArrayList<>();
	for (int i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			factors.add(i);
			n /= i;
		}
	}
	if (n > 1) { factors.add(n); }
	return factors;
}

from typing import List
 
 
def factor(n: int) -> List[int]:
	ret = []
	i = 2
	while i * i <= n:
		while n % i == 0:
			ret.append(i)
			n //= i
		i += 1
	if n > 1:
		ret.append(n)
	return ret

Este algoritmo corre en tiempo $\mathcal{O}(\sqrt{n})$, porque el bucle for comprueba divisibilidad para a lo sumo $\sqrt{n}$ valores. Aunque hay un bucle while dentro del bucle for, dividir $n$ por $i$ reduce rápidamente el valor de $n$, lo que significa que el bucle for exterior corre menos iteraciones, lo cual de hecho acelera el código.

Veamos un ejemplo de cómo funciona este algoritmo, para $n = 252$.

En este punto, el bucle for termina, porque $i$ ya es 3, que es mayor que $\lfloor \sqrt{7} \rfloor$. En el último paso, añadimos $7$ a la lista de factores $v$, porque de otro modo no se añadiría, para una factorización prima final de $\{2, 2, 3, 3, 7\}$.

Solución - Counting Divisors

La solución más directa es simplemente hacer lo que el problema nos pide: para cada $x$, hallar el número de divisores de $x$ en tiempo $\mathcal{O}(\sqrt x)$.

#include <iostream>
 
using namespace std;
 
int main() {
	int n;
	cin >> n;
	for (int q = 0; q < n; q++) {
		int x;
		int div_num = 0;
		cin >> x;
		for (int i = 1; i * i <= x; i++) {
			if (x % i == 0) { div_num += i * i == x ? 1 : 2; }
		}
		cout << div_num << '\n';
	}
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Divisors {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int queryNum = Integer.parseInt(read.readLine());
		StringBuilder ans = new StringBuilder();
		for (int q = 0; q < queryNum; q++) {
			int x = Integer.parseInt(read.readLine());
			int divisors = 0;
			for (int i = 1; i * i <= n; i++) {
				if (x % i == 0) { divisors += i * i == x ? 1 : 2; }
			}
			ans.append(divisors).append('\n');
		}
		System.out.print(ans);
	}
}

ans = []
for _ in range(int(input())):
	div_num = 0
	x = int(input())
	i = 1
	while i * i <= x:
		if x % i == 0:
			div_num += 1 if i**2 == x else 2
		i += 1
	ans.append(div_num)
 
print("\n".join(str(i) for i in ans))

Esta solución corre en tiempo $\mathcal{O}(n \sqrt x)$, que es justo lo bastante rápida para obtener AC. Sin embargo, de hecho podemos acelerar esto para obtener una solución $\mathcal{O}((x + n) \log x)$.

Primero, discutamos una propiedad importante de la factorización prima. Consideremos:

Entonces el número de divisores de $x$ es simplemente $(a_1 + 1) \cdot (a_2 + 1) \cdots (a_k + 1)$.

¿Por qué es esto cierto? El exponente de $p_i$ en cualquier divisor de $x$ debe estar en el rango $[0, a_i]$ y cada exponente distinto resulta en un conjunto distinto de divisores, así que cada $p_i$ contribuye $a_i + 1$ al producto.

$x$ puede tener $\mathcal{O}(\log x)$ factores primos distintos, así que si podemos hallar la factorización prima de $x$ de forma eficiente, podemos usarla con la propiedad de arriba para responder consultas en tiempo $\mathcal{O}(\log x)$ en lugar del tiempo $\mathcal{O}(\sqrt x)$ anterior.

Así es como hallamos la factorización prima de $x$ en tiempo $\mathcal{O}(\log x)$ con preprocesamiento $\mathcal{O}(x \log x)$:

1. Para cada $k \leq 10^6$, hallar algún número primo que divida a $k$. Para hallarlo, podemos usar la Criba de Eratóstenes  que corre en $\mathcal{O}(n \log n)$, donde $n$ es el mayor de los números que consideramos. También hay una versión de la criba que corre en tiempo lineal , pero no la necesitaremos.
2. Podemos hallar la factorización prima de $x$ dividiéndolo repetidamente por los números primos que calculamos antes hasta que $x = 1$.

Usar este método nos da el siguiente código:

#include <iostream>
 
using namespace std;
 
const int MAX_N = 1e6;
// max_div[i] contains the largest prime that goes into i
int max_div[MAX_N + 1];
 
int main() {
	for (int i = 2; i <= MAX_N; i++) {
		if (max_div[i] == 0) {
			for (int j = i; j <= MAX_N; j += i) { max_div[j] = i; }
		}
	}
 
	int n;
	cin >> n;
 
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		int div_num = 1;
		while (x != 1) {
			/*
			 * get the largest prime that can divide x and see
			 * how many times it goes into x (stored in count)
			 */
			int prime = max_div[x];
			int count = 0;
			while (x % prime == 0) {
				count++;
				x /= prime;
			}
			div_num *= count + 1;
		}
		cout << div_num << '\n';
	}
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Divisors {
	private static final int MAX_N = (int)Math.pow(10, 6);
	public static void main(String[] args) throws IOException {
		// maxDiv[i] contains the largest prime that can divide i
		int[] maxDiv = new int[MAX_N + 1];
		for (int i = 2; i <= MAX_N; i++) {
			if (maxDiv[i] == 0) {
				for (int j = i; j <= MAX_N; j += i) { maxDiv[j] = i; }
			}
		}
 
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int queryNum = Integer.parseInt(read.readLine());
		StringBuilder ans = new StringBuilder();
		for (int q = 0; q < queryNum; q++) {
			int x = Integer.parseInt(read.readLine());
			int factNum = 1;
			while (x != 1) {
				/*
				 * get the largest prime that can divide x and see
				 * how many times it goes into x (stored in count)
				 */
				int prime = maxDiv[x];
				int count = 0;
				while (x % prime == 0) {
					count++;
					x /= prime;
				}
				factNum *= count + 1;
			}
			ans.append(factNum).append('\n');
		}
		System.out.print(ans);
	}
}

MAX_N = 10**6
 
# max_div[i] contains the largest prime that can go into i
max_div = [0 for _ in range(MAX_N + 1)]
for i in range(2, MAX_N + 1):
	if max_div[i] == 0:
		for j in range(i, MAX_N + 1, i):
			max_div[j] = i
 
ans = []
for _ in range(int(input())):
	n = int(input())
	div_num = 1
	while n != 1:
		"""
		get the largest prime that can divide x and see
		how many times it goes into x (stored in count)
		"""
		largest = max_div[n]
		count = 0
		while n % largest == 0:
			count += 1
			n //= largest
		div_num *= count + 1
	ans.append(div_num)
 
print("\n".join(str(i) for i in ans))

MCD y MCM

MCD

El máximo común divisor (MCD / GCD) de dos enteros $a$ y $b$ es el mayor entero que es factor tanto de $a$ como de $b$. Para hallar el MCD de dos enteros no negativos, usamos el algoritmo de Euclides, que es el siguiente:

Este algoritmo se puede implementar con una función recursiva como sigue:

public int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

def gcd(a: int, b: int) -> int:
	return a if b == 0 else gcd(b, a % b)

Esta función corre en tiempo $\mathcal{O}(\log ab)$ porque $a\le b \implies b\pmod a <\frac{b}{2}$.

El peor caso para el algoritmo de Euclides es cuando $a$ y $b$ son números de Fibonacci consecutivos $F_n$ y $F_{n + 1}$. En este caso, el algoritmo calculará que $\gcd(F_n, F_{n + 1}) = \gcd(F_{n - 1}, F_n) = \dots = \gcd(0, F_1)$. Esto toma un total de $n+1$ llamadas, que es proporcional a $\log \left(F_n F_{n+1}\right)$.

MCM

El mínimo común múltiplo (MCM / LCM) de dos enteros $a$ y $b$ es el menor entero divisible tanto por $a$ como por $b$. El MCM se puede calcular con el MCD usando esta propiedad:

Además, estas dos funciones son asociativas, lo que significa que si queremos tomar el MCD o el MCM de más de dos elementos, podemos hacerlo de a dos, en cualquier orden. Por ejemplo,

Función φ de Euler

Propiedades

La función φ de Euler — escrita usando phi $\phi(n)$ — cuenta el número de enteros positivos en el intervalo $[1,n]$ que son coprimos con $n$. Dos números $a$ y $b$ son coprimos si su máximo común divisor es igual a 1, es decir, $gcd(a,b)=1$.

Aquí están los valores de $\phi(n)$ para los primeros 20 números:

La función totiente es multiplicativa, lo que significa que $\phi(nm)=\phi(n) \cdot \phi(m)$, donde $n$ y $m$ son coprimos — $gcd(n, m)=1$. Por ejemplo $\phi(15)=\phi(3 \cdot 5)=\phi(3) \cdot \phi(5) = 2 \cdot 4 = 8$.

Veamos algunos casos borde de $\phi(n)$:

• Si n es un número primo entonces $\phi(n)=n-1$ porque $gcd(n, x)=1$ para todo $1 \leq x < n$
• Si n es una potencia de un número primo, $n=p^q$ donde p es un número primo y $1 \leq q$ entonces
  hay exactamente $p^{q-1}$ números divisibles por $p$, así que $\phi(p^q)=p^{q} - p^{q-1} = p^{q-1}(p - 1)$

Usando la propiedad multiplicativa y el último caso borde podemos computar el valor de $\phi(n)$ a partir de la factorización del número $n$. Sea la factorización $n=p_1^{q_1} \cdot p_2^{q_2} \cdot \ldots \cdot p_k^{q_k}$ donde $p_i$ es un factor primo de $n$, entonces:

Abajo hay una implementación para factorizar en $\mathcal{O}(\sqrt{n})$. Puede ser un poco complicado entender por qué restamos $ans/p$ de $ans$. Por ejemplo $ans=p^q \cdot x$, donde $p$ es un factor primo y $x$ es el resto de la factorización prima. Al restar $\frac{ans}{p}=p^{q-1} \cdot x$ terminamos con: $p^q \cdot x - p^{q-1} \cdot x = p^{q-1} \cdot x \cdot (p - 1)$, que es exactamente la forma de $\phi(n)$ descrita unas líneas arriba.

int phi(int n) {
	int ans = n;
	for (int p = 2; p * p <= n; p++) {
		if (n % p == 0) {
			while (n % p == 0) { n /= p; }
			ans -= ans / p;
		}
	}
	if (n > 1) { ans -= ans / n; }
	return ans;
}

public static int phi(int n) {
	int ans = n;
	for (int p = 2; p * p <= n; p++) {
		if (n % p == 0) {
			while (n % p == 0) { n /= p; }
			ans -= ans / p;
		}
	}
 
	if (n > 1) { ans -= ans / n; }
	return ans;
}

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

Por lo general en los problemas necesitamos precomputar el totiente de todos los números entre $1$ y $n$; entonces factorizar no es eficiente. La idea es la misma que la Criba de Eratóstenes. Como es casi lo mismo que la Criba de Eratóstenes, la complejidad temporal será: $\mathcal{O}(N\log\log{N})$.

void precompute() {
	for (int i = 1; i < MAX_N; i++) { phi[i] = i; }
	for (int i = 2; i < MAX_N; i++) {
		// If i is prime
		if (phi[i] == i) {
			for (int j = i; j < MAX_N; j += i) { phi[j] -= phi[j] / i; }
		}
	}
}

public static void precompute() {
	for (int i = 1; i < MAX_N; i++) { phi[i] = i; }
 
	for (int i = 2; i < MAX_N; i++) {
		// If i is prime
		if (phi[i] == i) {
			for (int j = i; j < MAX_N; j += i) { phi[j] -= phi[j] / i; }
		}
	}
}

def precompute():
	for i in range(1, MAX_N):
		phi[i] = i
 
	for i in range(2, MAX_N):
		# If i is prime
		if phi[i] == i:
			for j in range(i, MAX_N, i):
				phi[j] -= phi[j] // i

Solución

Se nos pide computar la suma de MCDs de todos los pares $(i, j)$ tales que $1 \le i < j \le n$:

Definamos una función auxiliar $f(n)$ que computa la suma de MCDs para un segundo elemento fijo $n$:

Esta función suma $\gcd(i, n)$ para todo $i \le n$. Los términos donde $\gcd(i, n) = d$ son exactamente aquellos donde $d$ divide a $n$ y $\gcd(\frac{i}{d}, \frac{n}{d}) = 1$. El número de tales enteros $i$ lo da la función φ de Euler $\phi(\frac{n}{d})$. Así, podemos reescribir $f(n)$ como una suma sobre los divisores de $n$:

Podemos computar $f(n)$ para todo $n$ hasta $10^6$ de forma eficiente. En lugar de factorizar cada número, iteramos por cada posible divisor $i$ y actualizamos todos sus múltiplos $j$. Para un $i$ fijo, añadimos la contribución $i \cdot \phi(\frac{j}{i})$ a $f(j)$ para todos los $j$ que son múltiplos de $i$.

Finalmente, el problema pide pares donde $i < j$. El valor $f(j)$ incluye el caso $i=j$ (donde $\gcd(j, j) = j$), que debemos excluir. La respuesta para un $n$ dado es la suma de prefijos de estos valores ajustados:

La complejidad total de esta precomputación está acotada por la suma de la serie armónica:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX_N = 1e6;
 
ll phi[MAX_N + 1];
ll f[MAX_N + 1];
ll sum[MAX_N + 1];
 
int main() {
	// compute phi using sieve
	for (int i = 1; i <= MAX_N; i++) phi[i] = i;
 
	for (int i = 2; i <= MAX_N; i++)
		if (phi[i] == i)
			for (int j = i; j <= MAX_N; j += i) phi[j] -= phi[j] / i;
 
	// compute f[j]
	for (int i = 1; i <= MAX_N; i++)
		for (int j = i; j <= MAX_N; j += i) f[j] += 1LL * i * phi[j / i];
 
	// prefix sums for answers (remove diagonal a=b)
	for (int i = 1; i <= MAX_N; i++) sum[i] = sum[i - 1] + f[i] - i;
 
	int n;
	while (cin >> n) {
		if (n == 0) break;
		cout << sum[n] << '\n';
	}
 
	return 0;
}

Problemas