MOMOS - FEASTOFPIGS

Explicación

Es muy importante notar que los casos de prueba se dividen en dos tipos según las restricciones:

El primer caso ( $N \le 10^6$ y $K \le 100$ ) se puede resolver usando una criba.
En el segundo caso ( $N \le 10^{14}$ y $K \le 20$ ) una criba usaría demasiada memoria por el límite de $N$ . Por otro lado, la cantidad de momos es bastante pequeña, así que podemos aplicar el clásico PIE. Usaremos máscaras de bits para iterar sobre todos los subconjuntos de momos. Tomamos el mínimo común múltiplo de los valores contenidos en la máscara y actualizamos la respuesta en consecuencia.

Implementación

Complejidad temporal: $\mathcal{O}(NK)$ cuando $N \le 10^6$ y $K \le 100$ , $\mathcal{O}(K \cdot 2^k)$ cuando $K \le 20$ y $N \le 10^{14}$ .

C++


#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXK = 100;
const int MAXN = 1e6;
 
long long n, k;
long long v[MAXK + 1];
bool momo[MAXN + 1];
 
// Sieve solution
void solve1() {
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < n; j += v[i]) { momo[j] = true; }
	}
	long long cnt = 0;
	for (int i = 0; i < n; i++) { cnt += momo[i]; }
	cout << n - cnt << '\n';
}
 
// Inclusion-Exclusion solution
void solve2() {
	long long ans = n - 1;
	for (int mask = 1; mask < (1 << k); mask++) {
		long long lcm = 1;
		int bits = __builtin_popcount(mask);
		for (int i = 0; (1 << i) <= mask; i++) {
			if (mask & (1 << i)) {
				// Avoid overflow
				if (lcm / __gcd(lcm, v[i]) > LLONG_MAX / v[i]) {
					lcm = n;
					break;
				}
				// Use the formula: lcm(x, y) = x * y / gcd(x, y)
				lcm = lcm / __gcd(lcm, v[i]) * v[i];
			}
		}
		ans = ans + (bits % 2 == 1 ? -1 : 1) * ((n - 1) / lcm);
	}
	cout << ans << '\n';
}
 
int main() {
 
	cin >> n >> k;
 
	for (int i = 0; i < k; i++) { cin >> v[i]; }
 
	if (k > 20) {
		solve1();
	} else {
		solve2();
	}
}