Nota ~1~: La cantidad de números desde ~1~ hasta ~n~ que son divididos por ~d~ es ~\lfloor{\frac{n}{d}}\rfloor~.

Nota ~2~: El principio de inclusión y exclusión afirma que,

$$\displaystyle |A_1 \cup A_2 \cup \dots \cup A_n| = \sum_{i} |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{i < j < k} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1}|A_1 \cap A_2 \cap \dots \cap A_n|.$$

Definamos, ~A_{n, d} = \lbrace{x: \; 1 \le x \le n \; \text{y} \; d \nmid x}\rbrace~ (o sea, que ~A_{n, d}~ es el conjunto de los números desde ~1~ hasta ~n~ que no son divididos por ~d~). Utilizando la nota ~1~ podemos calcular ~|A_{n, d}|~ como ~|A_{n, d}| = n - \lfloor{\frac{n}{d}}\rfloor~. Por comodidad, en lo adelante llamaré a ~|A_{n,d}|~ como ~|A_d|~

Para resolver el problema debemos calcular ~|A_2 \cup A_3 \cup A_5|~, lo cual puede ser hecho utilizando la nota ~2~ (el principio de inclusión y exclusión),

$$\displaystyle |A_2 \cup A_3 \cup A_5| = |A_2| + |A_3| + |A_5| - |A_2 \cap A_3| - |A_2 \cap A_5| - |A_3 \cap A_5| + |A_2 \cap A_3 \cap A_5|.$$

Para calcular lo anterior, necesitamos calcular la intersección entre dos conjuntos, en este problema: ~A_{d_1} \cap A_{d_2} = A_{d_1 \times d_2}~. De esta forma,

$$\displaystyle |A_2 \cup A_3 \cup A_5| = |A_2| + |A_3| + |A_5| - |A_{2 \times 3}| - |A_{2 \times 5}| - |A_{3 \times 5}| + |A_{2 \times 3 \times 5}|$$ $$\displaystyle \qquad \; \; \; = |A_2| + |A_3| + |A_5| - |A_{6}| - |A_{10}| - |A_{15}| + |A_{30}|.$$

Código de ejemplo 1: ~O(1)~

int n; cin >> n;

auto f = [&](int d) { // f(d) = |A_d|
  return n - n / d;
};

int res = f(2) + f(3) + f(5) - f(6) - f(10) - f(15) + f(30);

cout << res << endl;

Código de ejemplo 2 (con máscara de bits): ~O(2^k \times k)~ donde ~k = |\lbrace{2, 3, 5}\rbrace| = 3~

int n; cin >> n;

auto f = [&](int d) { // f(d) = |A_d|
  return n - n / d;
};

vector<int> nums = {2, 3, 5};

int res = 0;
for (int mask = 1; mask < (1 << 3); mask++) {
  int prod = 1, parity = 0;
  for (int i = 0; i < 3; i++) {
    if ((mask >> i) & 1) {
      prod *= nums[i];
      parity = (parity + 1) % 2;
    }
  }

  if (parity == 0) {
    res -= f(prod);
  } else {
    res += f(prod);
  }
}

cout << res << endl;

Otro problema que puede ser resuelto usando el principio de inclusión y exclusión:

• Cuban Roulette: OCI19 1A