Skip to Content
CTRL K

Prime Multiples

Explicación

Podemos observar que, dado cualquier entero cc, la cantidad de enteros divisibles por él entre 1 y NN es ⌊Nc⌋\lfloor\frac{N}{c}\rfloor

Si consideramos cada primo por separado y hallamos cuántos múltiplos tiene, veremos que hay un solapamiento para cada número que es múltiplo de dos primos. Por ejemplo, 1010 es múltiplo de 22 y de 55, así que si sumáramos todos los ⌊Na[i]⌋\lfloor\frac{N}{a[i]}\rfloor para todos los primos, todavía tendríamos que restar ⌊Na[i]⋅a[j]⌋\lfloor\frac{N}{a[i] \cdot a[j]}\rfloor para todos los i y j distintos.

De forma similar, esta resta tendría un solapamiento para cada número que es múltiplo de tres primos. Un ejemplo sería 3030, múltiplo de 22, 33 y 55, de modo que habríamos restado todos los múltiplos de 66, 1010 y 1515, lo que implica que debemos volver a sumar la cantidad de enteros que son múltiplos de tres primos. Esto se extiende a todo el arreglo, y nos obliga a alternar sumas y restas según cuántos primos estemos multiplicando.

Considerando solo 3030, el ejemplo completo sería que nuestra respuesta se suma 33 veces por 22, 33 y 55 (subconjuntos del arreglo con 11 primo), luego se resta 33 veces por 66, 1010 y 1515 (subconjuntos del arreglo con 22 primos), y por último se suma una vez por 3030 (subconjunto del arreglo con 33 primos), de modo que en total se cuenta solo una vez.

Para implementarlo, debemos recorrer cada subconjunto del arreglo y sumar la cantidad de múltiplos si el número de primos no es divisible por 2, y restar en caso contrario. Esto se conoce como el principio de inclusión-exclusión . Para iterar por todos los subconjuntos del arreglo, podemos iterar de 11 a 2K−12^K-1 y usar operadores de bits para hallar qué índices estamos usando.

Implementación

Complejidad temporal: O(K⋅2K)\mathcal{O}(K\cdot 2^K)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
	ll n, k;
	cin >> n >> k;
	vector<ll> a(k);
	for (int i = 0; i < k; i++) cin >> a[i];
 
	ll ans = 0;
	for (ll i = 1; i < (1 << k); i++) {
		ll prime_product = 1;
		for (ll j = 0; j < k; j++) {
			// comprobar si estamos usando a[j] en este número
			if (i & (1 << j)) {
				// comprobar que no haya desbordamiento; si lo hay, asignar
				// prime_product a N+1 para que ans no cambie
				if (prime_product > n / a[j]) {
					prime_product = n + 1;
					break;
				}
				prime_product *= a[j];
			}
		}
 
		//__builtin_popcount da la cantidad de 1's en la representación binaria,
		// que también es la cantidad de primos que hemos multiplicado
		if (__builtin_popcount(i) % 2) {
			ans += n / prime_product;
		} else {
			ans -= n / prime_product;
		}
	}
 
	cout << ans << endl;
}
import java.util.*;
 
public class PrimeMultiples {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		int k = sc.nextInt();
		long[] a = new long[k];
		for (int i = 0; i < k; i++) { a[i] = sc.nextLong(); }
 
		long ans = 0;
		for (int i = 1; i < (1 << k); i++) {
			long primeProduct = 1;
			for (int j = 0; j < k; j++) {
				// comprobar si estamos usando a[j] en este número
				if ((i & (1 << j)) != 0) {
					// comprobar que no haya desbordamiento; si lo hay, asignar
					// primeProduct a n+1 para que ans no cambie
					if (primeProduct > n / a[j]) {
						primeProduct = n + 1;
						break;
					}
					primeProduct *= a[j];
				}
			}
 
			// Integer.bitCount da la cantidad de 1's en la representación binaria,
			// que también es la cantidad de primos que hemos multiplicado
			if (Integer.bitCount(i) % 2 == 1) {
				ans += n / primeProduct;
			} else {
				ans -= n / primeProduct;
			}
		}
 
		System.out.println(ans);
	}
}
n, k = map(int, input().split())
a = list(map(int, input().split()))
 
ans = 0
for i in range(1, 1 << k):
	prime_product = 1
 
	for j in range(k):
		# comprobar si estamos usando a[j] en este número
		if i & (1 << j):
			prime_product *= a[j]
 
	# convertir a representación binaria y contar la cantidad de 1's,
	# que es igual a la cantidad de primos que hemos multiplicado
	if bin(i).count("1") % 2:
		ans += n // prime_product
	else:
		ans -= n // prime_product
 
print(ans)
Fundamentos