Skip to Content
CTRL K

Make It One

Pista 1

Intentemos construir una cota superior sobre el número máximo de elementos necesarios para un GCD de 1.

Pista 2

¿Cuál es el número máximo de factores primos distintos que se pueden meter en un número que es a lo sumo 3⋅1053 \cdot 10^5?

Pista 3

Sea \texttt{gcd\\_ways}[i][\texttt{gcd}] el número de formas de seleccionar un subconjunto de tamaño ii del arreglo dado con GCD gcd\texttt{gcd}.

Pista 4

Calcular \texttt{gcd\\_ways}[i] a partir de \texttt{gcd\\_ways}[i-1] parece casi imposible. ¿Habrá una forma alternativa de calcularlo? ¿Y si lo calculáramos a partir del propio \texttt{gcd\\_ways}[i]?

Solución

Editorial oficial (C++) 

Explicación

Una cota superior de la respuesta

Nótese que un número menor que 3⋅1053 \cdot 10^5 tiene a lo sumo 6 factores primos. ¡Hay que programarlo en el lenguaje preferido si esto no convence!

Ahora, podemos deducir que cualquier respuesta al problema debe ser menor que 7 (excluyendo el caso en que es imposible).

Para ver por qué es cierto, digamos que teníamos un elemento con 6 factores primos (la cantidad máxima) en el subconjunto que estábamos construyendo. Con un elemento adicional, el GCD de ese subconjunto debería tener 1 factor primo menos. Si no reduce el número de factores primos, no tiene sentido incluirlo en primer lugar.

Programación dinámica

Ahora, sea \texttt{gcd\\_ways}[i][\texttt{gcd}] el número de formas de seleccionar un subconjunto de tamaño ii del arreglo dado con GCD gcd\texttt{gcd} (si se leyeron las pistas, esto ya debería haberse visto).

Calculamos \texttt{gcd\\_ways}[i][\texttt{gcd}] no a partir de \texttt{gcd\\_ways}[i-1], ¡sino a partir del propio \texttt{gcd\\_ways}[i]!

Nuestra transición es la siguiente:

\texttt{gcd\\_ways}[i][\texttt{gcd}]=\binom{x}{i}-\sum_{k=2}^{\infty}{\texttt{gcd\\_ways}[i][k \cdot \texttt{gcd}]}

En esta fórmula, xx es el número de elementos de nuestro conjunto que son divisibles por gcd\texttt{gcd}. Inicialmente contamos el número crudo de subconjuntos de tamaño ii con el binomial, pero nótese que en realidad sobrecontamos: es posible que hayamos incluido un subconjunto con GCD 2k2k

Para remediarlo, restamos la suma sobre todos los múltiplos de gcd\texttt{gcd} para corregir este error inicial.

Iterando ii de 1 a 7 y gcd\texttt{gcd} de MM a 1, donde MM es el elemento máximo dado en la entrada, ahora podemos comprobar si hay un subconjunto de tamaño ii con GCD 1 comprobando \texttt{gcd\\_ways}[i][1].

Implementación

Complejidad temporal: O(log⁡M(N+M))\mathcal{O}(\log M (N + M)), donde MM es el mismo de arriba.

from math import comb
 
MOD = 10**9 + 7
ANS_UB = 7
 
n = int(input())
 
nums = {int(i) for i in input().split()}
max_ = max(nums)
 
div_by_num = [0 for _ in range(max_ + 1)]
for d in range(1, max_ + 1):
	for mul in range(d, max_ + 1, d):
		div_by_num[d] += mul in nums
 
for i in range(1, ANS_UB + 1):
	gcd_ways = [0 for _ in range(max_ + 1)]
	for j in range(max_, 0, -1):
		val = comb(div_by_num[j], i)
		for j_mul in range(2 * j, max_ + 1, j):
			val -= gcd_ways[j_mul]
		gcd_ways[j] = val
 
	if gcd_ways[1] > 0:
		print(i)
		break
else:
	print(-1)

Como C++ no puede almacenar números enormes, hay que usar un módulo para hacer los cálculos.

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
constexpr int MOD = 1e9 + 7;
constexpr int ANS_UB = 7;
 
long long pow(long long base, long long exp) {
	base %= MOD;
	long long res = 1;
	while (exp > 0) {
		if (exp % 2 == 1) { res = res * base % MOD; }
		base = base * base % MOD;
		exp /= 2;
	}
	return res;
}
 
long long mod_inv(long long n) { return pow(n, MOD - 2); }
 
int main() {
	int n;
	std::cin >> n;
 
	vector<long long> fact(n + 1);
	fact[0] = 1;
	for (int i = 1; i <= n; i++) { fact[i] = (fact[i - 1] * i) % MOD; }
	auto comb = [&](int n, int k) {
		if (n < k) { return 0LL; }
		return fact[n] * mod_inv(fact[k] * fact[n - k] % MOD) % MOD;
	};
 
	std::set<int> nums;
	for (int i = 0; i < n; i++) {
		int x;
		std::cin >> x;
		nums.insert(x);
	}
 
	int max = *std::max_element(nums.begin(), nums.end());
	vector<int> div_by_num(max + 1);
	for (int d = 1; d <= max; d++) {
		for (int mul = d; mul <= max; mul += d) { div_by_num[d] += nums.count(mul); }
	}
 
	for (int i = 1; i <= ANS_UB; i++) {
		vector<long long> gcd_ways(max + 1);
		for (int j = max; j >= 1; j--) {
			long long val = comb(div_by_num[j], i);
			for (int j_mul = 2 * j; j_mul <= max; j_mul += j) {
				val = (val - gcd_ways[j_mul] + MOD) % MOD;
			}
			gcd_ways[j] = val;
		}
 
		if (gcd_ways[1] > 0) {
			cout << i << endl;
			return 0;
		}
	}
 
	cout << -1 << endl;
}
Fundamentos