Inclusion-Exclusion

Count elements satisfying none/any of n properties using bitmask inclusion-exclusion.

[Combinatorics]|

Jul 9, 2026

|explanatory_notes.md|

#inclusion-exclusion#coprime#bitmask#counting

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int coprimeCount(int n, int r) {
  vector<int> p;
  for (int i = 2; (ll)i * i <= n; i++) {
    if (n % i == 0) {
      p.push_back(i);
      while (n % i == 0) n /= i;
    }
  }
  if (n > 1) p.push_back(n);

  int sum = 0;
  for (int msk = 1; msk < (1 << (int)p.size()); msk++) {
    int mult = 1, bits = __builtin_popcount(msk);
    for (int i = 0; i < (int)p.size(); i++)
      if (msk >> i & 1) mult *= p[i];
    if (bits & 1)
      sum += r / mult;
    else
      sum -= r / mult;
  }
  return r - sum;
}

int divisibleByAny(int n, vector<int>& a) {
  int m = a.size(), sum = 0;
  for (int msk = 1; msk < (1 << m); msk++) {
    ll lcm = 1;
    int bits = __builtin_popcount(msk);
    bool overflow = false;
    for (int i = 0; i < m; i++) {
      if (msk >> i & 1) {
        lcm = lcm / __gcd(lcm, (ll)a[i]) * a[i];
        if (lcm > n) {
          overflow = true;
          break;
        }
      }
    }
    if (overflow) continue;
    if (bits & 1)
      sum += n / lcm;
    else
      sum -= n / lcm;
  }
  return sum;
}

50 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Inclusion-Exclusion Principle

Corrects over-counting by alternately adding and subtracting intersections.

Formula

|A_1 \cup \cdots \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \cdots + (-1)^{n+1} |A_1 \cap \cdots \cap A_n|

Bitmask Approach

Iterate all $2^p$ subsets. For each subset of size $k$ : add if $k$ is odd, subtract if even.

Functions

coprimeCount(n, r) — count integers in

[1, r]

coprime to

n

divisibleByAny(n, a) — count integers in

[1, n]

divisible by at least one element of

a

(uses LCM for intersections)

When to Use

"How many from

1

N

are NOT divisible by any of these?"

Coprime counting, derangements

Property set must be small (

p \le 20

) for

2^p

enumeration

Complexity

Time —

O(2^p \cdot p)

Space —

O(p)