Professional Layer

Sea $g$ el GCD de los valores del arreglo, $\gcd(a_1, \dots, a_n)$. ¿Cuál es la cota sobre el número de primos en la factorización de $g$?

Si jugamos un juez, deberíamos intentar eliminar un conjunto específico de primos de su valor de $a_i$ en una partida.

Sea $m$ el número de primos en la factorización de $g$. Como $m \leq 11$, podemos considerar DP con máscaras de bits, y potencialmente una DP de fusión de subconjuntos $\mathcal{O}(3^M)$.

Con $N \leq 10^6$, ejecutar una DP por juez es demasiado lento. ¿Cómo podemos comprimir el número de jueces a una cantidad más manejable?

Para cada valor de $a_i$, quitamos todos los factores primos que no están en la factorización de $g$. Con las cotas dadas, hay a lo sumo $12000$ valores distintos de $a_i$ en cualquier entrada. Como cada juez que juguemos debería quitar al menos un primo de $g$, solo consideramos los $m$ jueces más baratos para cada valor de $a_i$.

Sin embargo, hacer de forma naive una DP de fusión de subconjuntos en cada uno corre en $\mathcal{O}(MK \cdot 3^M)$, donde $K$ es el número de valores distintos de $a_i$. ¿Cómo podemos reducir el número de transiciones de DP a considerar?

Explicación

Sea $g$ el GCD de los valores del arreglo, $p$ el conjunto de primos en la factorización de $g$, y $m = |p|$. Si $g=1$, entonces la respuesta es $0$.

Si jugamos un juez, deberíamos eliminar un subconjunto específico de primos de $p$ de su valor de $a_i$. Como el producto de los primeros $12$ primos ya supera $10^{12}$, tenemos

lo que motiva un enfoque con máscaras de bits.

Una DP naive con máscaras tendría $\text{dp}[i][\text{mask}]$ como la suma mínima de valores de experiencia para quitar todos los primos en $\text{mask}$ con $i$ jueces. Esto requeriría actualizar nuestra tabla de DP por cada juez, lo que da una complejidad temporal de $\mathcal{O}(NM \cdot 3^M)$, que es demasiado lenta para este problema.

Comprimir jueces

Para cada valor de $a_i$, quitamos todos los factores primos que no están en la factorización de $g$, ya que no afectan la respuesta. Después de quitar los primos innecesarios, hay a lo sumo $12000$ valores distintos de $a_i$ en cualquier entrada.

Cualquier juez útil debe eliminar al menos un factor primo de $g$, así que jugamos a lo sumo $m$ jueces. Por lo tanto, consideramos a lo sumo $m$ jueces para cada valor único de $a_i$, y siempre es óptimo elegir los de menor experiencia.

Esto reduce el número de jueces a a lo sumo $mK$, y la complejidad de nuestra DP a $\mathcal{O}(M^2 K \cdot 3^M)$, donde $K$ es el número de valores únicos de $a_i$.

Optimizar transiciones válidas

Para eliminar un conjunto de primos $S$ de un valor de $a_i$, debemos dividir todas las potencias de primos relevantes. Si el producto de estas potencias de primos es $\leq K$, entonces quitar este conjunto de primos de $g$ es posible.

Formalmente, sea $q_j = p_j^{v_{p_j}(a_i)}$ la potencia completa del primo $p_j$ que divide a $a_i$. Podemos quitar un conjunto $S$ si

ya que este producto es el menor divisor de $a_i$ que contiene cada primo de $S$.

El siguiente código calcula de forma eficiente el costo de quitar cada subconjunto de $p$:

std::vector<ll> mask_cost(1 << m, 1);
for (int j = 1; j < (1 << m); j++) {
	// we exclude least significant bit, and calculate contribution
	// from that bit in our cost to remove it
	int lsb = __builtin_ctz(j);
	mask_cost[j] = mask_cost[j ^ (1 << lsb)];
 
	ll val = a[i];
	while (val % primes[lsb] == 0) {
		// since mask_cost grows fast, overflow guard is needed!
		if (mask_cost[j] > INF / primes[lsb]) break;
 
		val /= primes[lsb];
		mask_cost[j] *= primes[lsb];
	}
 
	if (mask_cost[j] <= k) {
		// process this mask's transition by updating the DP table
	}
}

Como redujimos el número de jueces a considerar, podemos permitirnos calcular todo el costo de quitar subconjuntos para cada juez. Sin embargo, el número de transiciones sigue siendo demasiado grande.

Una vez más, podemos reducir el número de transiciones con la cota sobre el número máximo de jueces. Un estado de transición consiste en $(\text{mask}, \text{judge})$, que tiene hasta $MK \cdot 2^M$ combinaciones. ¡Pero solo necesitamos las $m$ mejores transiciones para cada máscara de transición! Esto reduce el número de transiciones a $\mathcal{O}(M \cdot 2^M)$.

Implementar la DP

El algoritmo general es el siguiente:

• Primero, quitamos todos los jueces redundantes, quedándonos con los $M$ jueces de menor experiencia para cada valor distinto de $a_i$. Esto da $\mathcal{O}(MK)$ jueces a considerar. Nótese que quitamos todas las potencias de primos que no están en $p$ de los valores de $a_i$.
• Calculamos todas las máscaras de transición posibles para cada juez restante. Para una máscara de transición posible, solo consideramos este juez si está entre los $m$ de menor experiencia con esta máscara. Calculamos inv(i), que guarda las máscaras donde el juez $i$ está entre los $m$ mejores.
• Como no podemos reutilizar jueces, iteramos sobre los jueces en orden, actualizando nuestra tabla de DP para las transiciones que cada juez provee.

El siguiente código muestra las transiciones de DP:

// dp[# of judges used][mask] = minimum sum of experiences
std::vector dp(m + 1, std::vector<ll>(1 << m, INF));
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
	for (int j = m; j >= 1; j--) {
		for (int mask : inv[i]) {
			for (int super = mask; super < (1 << m); super = (super + 1) | mask) {
				dp[j][super] = std::min(dp[j][super], dp[j - 1][super ^ mask] + e[i]);
			}
		}
	}
}

Implementación

Complejidad temporal: $\mathcal{O}(MK\cdot 2^M + M^2 \cdot 3^M)$, donde $K$ es el número de jueces distintos.

#include <bits/stdc++.h>
 
using ll = long long;
 
constexpr ll INF = 1e18;
 
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
 
	int n;
	ll k;
	std::cin >> n >> k;
 
	ll g = 0;
	std::vector<ll> a(n);
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
		g = std::gcd(g, a[i]);
	}
 
	std::vector<int> e(n);
	for (int i = 0; i < n; i++) { std::cin >> e[i]; }
 
	if (g == 1) {
		// we don't need to do anything
		std::cout << 0 << '\n';
		return 0;
	}
 
	// prime factorize the GCD
	std::vector<ll> primes;
	ll tmp = g;
	for (int i = 2; 1LL * i * i <= tmp; i++) {
		if (tmp % i == 0) {
			primes.push_back(i);
			while (tmp % i == 0) { tmp /= i; }
		}
	}
 
	if (tmp > 1) { primes.push_back(tmp); }
 
	const int m = primes.size();
 
	// we process items in sorted order for easier processing of
	// 'equivalent' judges (judges who cover same transition masks)
	std::vector<int> ord(n);
	std::iota(ord.begin(), ord.end(), 0);
	std::sort(ord.begin(), ord.end(),
	          [&](int x, int y) -> bool { return e[x] < e[y]; });
 
	std::map<ll, int> vis;
	std::vector<int> seen_masks(1 << m);
	std::vector<std::vector<int>> inv(n);
	for (int i : ord) {
		ll val = a[i];
 
		// calculate the product of prime powers for the
		// primes in our GCD (since only those primes matter)
		ll cost = 1;
		for (int j : primes) {
			while (val % j == 0) {
				cost *= j;
				val /= j;
			}
		}
 
		// we only use at most m equivalent judges
		if (vis[cost] >= m) continue;
		vis[cost]++;
 
		// mask_cost[mask] = division value to remove primes in mask from the GCD
		std::vector<ll> mask_cost(1 << m, 1);
		for (int j = 1; j < (1 << m); j++) {
			// we exclude least significant bit, and calculate contribution
			// from that bit in our cost to remove it
			int lsb = __builtin_ctz(j);
			mask_cost[j] = mask_cost[j ^ (1 << lsb)];
 
			val = a[i];
			while (val % primes[lsb] == 0) {
				// since mask_cost grows fast, overflow guard is needed!
				if (mask_cost[j] > INF / primes[lsb]) break;
 
				val /= primes[lsb];
				mask_cost[j] *= primes[lsb];
			}
 
			// for a given transition (i.e. a set of primes we can 'clear'),
			// we only care about the m cheapest judges for that transition
			if (mask_cost[j] <= k && seen_masks[j] < m) {
				seen_masks[j]++;
				inv[i].push_back(j);
			}
		}
	}
 
	// dp[# of judges used][mask] = minimum sum of experiences
	std::vector dp(m + 1, std::vector<ll>(1 << m, INF));
	dp[0][0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = m; j >= 1; j--) {
			for (int mask : inv[i]) {
				for (int super = mask; super < (1 << m); super = (super + 1) | mask) {
					dp[j][super] =
					    std::min(dp[j][super], dp[j - 1][super ^ mask] + e[i]);
				}
			}
		}
	}
 
	ll res = INF;
	for (int i = 0; i <= m; i++) {
		if (dp[i][(1 << m) - 1] < INF) { res = std::min(res, dp[i][(1 << m) - 1] * i); }
	}
 
	std::cout << (res < INF ? res : -1) << '\n';
}