Prime Gift

Pista 1

La solución prevista no tiene nada que ver con máscaras de bits. Intentemos explotar las cotas pequeñas de otras formas.

Pista 2

Miremos este problema e intentemos vincularlo con el original.

Solución

Editorial oficial (C++)

Explicación

En el espíritu del enfoque meet-in-the-middle, partamos el conjunto de números primos por la mitad. Para cada uno, hacemos un DFS de fuerza bruta para hallar todos los números menores que $10^{18}$ que tienen divisores primos solo en ese conjunto. Para evitar que un conjunto sea mucho más grande que el otro, alternamos entre el conjunto en el que ponemos números, como mostrará la implementación. Esto da dos arreglos que tienen a lo sumo alrededor de un millón de elementos.

Ahora, hacemos búsqueda binaria por el $k$ -ésimo número más pequeño. Nótese que este número será mayor o igual que exactamente $k$ productos por pares de los dos. Todos los números mayores que ese no tendrán menos, mientras que todos los números menores que ese no tendrán más.

Implementación

Complejidad temporal: $\mathcal{O}(\log \mathcal{M} \cdot (|D(A)| + |D(B)|))$ , donde $\mathcal{M}$ es la respuesta máxima posible.

C++


#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
 
using namespace std;
 
using ll = long long;
const ll MAX_ANSWER = 1e18;
 
// BeginCodeSnip{Binary Search (from the module)}
ll first_true(ll lo, ll hi, function<bool(ll)> f) {
	hi++;
	while (lo < hi) {
		ll mid = lo + (hi - lo) / 2;
		if (f(mid)) {
			hi = mid;
		} else {
			lo = mid + 1;
		}
	}
	return lo;
}
// EndCodeSnip
 
vector<long long> naive_search(vector<int> primes) {
	sort(primes.begin(), primes.end());
 
	vector<long long> ret;
	function<void(long long, int)> dfs = [&](long long prod, int at) {
		ret.push_back(prod);
		for (int i = at; i < primes.size(); i++) {
			// use division in comparison to prevent overflow
			if (MAX_ANSWER / primes[i] < prod) { break; }
			dfs(prod * primes[i], i);
		}
	};
	dfs(1, 0);
 
	return ret;
}
 
int main() {
	int n;
	cin >> n;
	vector<int> odds, evens;
	for (int i = 0; i < n; i++) {
		ll x;
		cin >> x;
		if (i % 2 == 0) {
			odds.push_back(x);
		} else {
			evens.push_back(x);
		}
	}
 
	// generate all numbers with only prime divisors from each list
	vector<ll> odd_nums = naive_search(odds);
	vector<ll> even_nums = naive_search(evens);
	sort(odd_nums.begin(), odd_nums.end());
	sort(even_nums.begin(), even_nums.end());
 
	int k;
	cin >> k;
	// Checks if x is greater than or equal to at least k pairwise products
	auto test = [&](ll x) {
		ll tot = 0;
 
		// Two pointers
		ll o_pt = lower_bound(odd_nums.begin(), odd_nums.end(), x) - odd_nums.begin();
		if (o_pt == odd_nums.size()) { o_pt--; }
 
		for (ll e : even_nums) {
			if (e > x) { break; }
			while (odd_nums[o_pt] > x / e) { o_pt--; }
			tot += o_pt + 1;
		}
 
		return tot >= k;
	};
 
	cout << first_true(1, MAX_ANSWER, test) << endl;
}