Principiul Includerii și Excluderii (PInEx)

PInEx e o tehnică de numărare care rezolvă probleme de forma: “câte elemente satisfac cel puțin una dintre condițiile P1, P2, ..., Pn?”

Ideea intuitivă: când adunăm mărimile mulțimilor, dublăm elementele din intersecții. Trebuie să scădem ce am adunat în plus. Dar scăzând perechile, scădem prea mult din tripletele comune. Trebuie să le adăugăm înapoi. Și așa mai departe.

Intuiția cu diagrame Venn

2 mulțimi

        ┌──────────────┐
        │      A       │
        │    ┌─────────┼─────┐
        │    │  A ∩ B  │     │
        │    │         │  B  │
        └────┼─────────┘     │
             │               │
             └───────────────┘

Dacă adunăm |A| + |B|, elementul din A ∩ B a fost numărat de două ori. Trebuie să-l scădem o dată.

|A ∪ B| = |A| + |B| - |A ∩ B|

|A| = 10
|B| = 8
|A ∩ B| = 3

|A ∪ B| = 10 + 8 - 3 = 15

3 mulțimi

Adunăm |A| + |B| + |C|. Fiecare element din:

• O singură mulțime → numărat 1 dată ✓
• Exact 2 mulțimi (A∩B, A∩C, B∩C fără A∩B∩C) → numărat 2 ori ✗ (trebuie 1)
• Toate 3 (A∩B∩C) → numărat 3 ori ✗ (trebuie 1)

Scădem |A∩B| + |A∩C| + |B∩C|. Acum:

• Elemente exact în 2: numărat 2-1 = 1 dată ✓
• Elemente în toate 3: numărat 3-3 = 0 dată ✗ (trebuie 1)

Adăugăm |A∩B∩C|:

• Elemente în toate 3: numărat 0+1 = 1 dată ✓

|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

Tabel cu câte ori e numărat fiecare element

Pentru 3 mulțimi:

Fiecare element e numărat exact o dată - exact cât trebuie pentru uniune.

Formula generală

Pentru n mulțimi:

|A₁ ∪ A₂ ∪ … ∪ Aₙ| = Σ|Aᵢ| - Σ|Aᵢ ∩ Aⱼ| + Σ|Aᵢ ∩ Aⱼ ∩ Aₖ| - … ± |A₁ ∩ … ∩ Aₙ|

Compact:

|A₁ ∪ ... ∪ Aₙ| = Σ (-1)^(|S|+1) * |∩(i ∈ S) Aᵢ|

unde suma e peste toate submulțimile nevide S ale lui {1, 2, ..., n}.

Semnul depinde de câte mulțimi intersectăm:

Semnul e (-1)^(k+1) pentru k mulțimi.

De ce funcționează? (demonstrația prin binom)

Σ (j=1..k) (-1)^(j+1) * C(k, j)
= -Σ (j=1..k) (-1)^j * C(k, j)
= -(Σ (j=0..k) (-1)^j * C(k, j) - 1)
= -(0 - 1)   // binomul lui Newton: (1-1)^k = 0
= 1

Problema clasică 1: numere divizibile

Enunț: Câte numere de la 1 la N sunt divizibile cu cel puțin unul dintre p1, p2, ..., pk (prime distincte)?

Soluția directă (fără PInEx)

Complicată - trebuie să tratăm suprapunerile manual. Pentru k prime, devine exponențial de greu.

Cu PInEx

Fie Aᵢ = mulțimea numerelor de la 1 la N divizibile cu pᵢ.

Observații cheie:

• |Aᵢ| = câte numere de la 1 la N sunt divizibile cu pᵢ = N / pᵢ (diviziune întreagă)
• |Aᵢ ∩ Aⱼ| = câte numere sunt divizibile cu amândouă = divizibile cu pᵢ * pⱼ (pentru prime distincte) = N / (pᵢ * pⱼ)
• În general, intersecția de j mulțimi = divizibile cu produsul = N / (pᵢ₁ * pᵢ₂ * ... * pᵢⱼ)

Formula:

Răspuns = ΣN/pᵢ - ΣN/(pᵢ*pⱼ) + ΣN/(pᵢ*pⱼ*pₖ) - ...

Exemplu: N = 30, prime {2, 3, 5}

Numere de la 1 la 30 divizibile cu 2: {2, 4, 6, ..., 30} → 15 numere
Numere divizibile cu 3: {3, 6, 9, ..., 30} → 10 numere
Numere divizibile cu 5: {5, 10, 15, 20, 25, 30} → 6 numere
Numere divizibile cu 6 (=2*3): {6, 12, 18, 24, 30} → 5 numere
Numere divizibile cu 10 (=2*5): {10, 20, 30} → 3 numere
Numere divizibile cu 15 (=3*5): {15, 30} → 2 numere
Numere divizibile cu 30 (=2*3*5): {30} → 1 număr

PInEx:

Răspuns = 15 + 10 + 6 - 5 - 3 - 2 + 1 = 22

22 numere de la 1 la 30 sunt divizibile cu 2, 3 sau 5.

Verificare: numere de la 1 la 30 care nu sunt divizibile cu niciun prim din {2,3,5}: {1, 7, 11, 13, 17, 19, 23, 29} → 8 numere. Deci 30 - 8 = 22 ✓

Implementare cu bitmask

Pentru k mulțimi, iterăm prin toate cele 2^k - 1 submulțimi nevide reprezentate ca bitmask:

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int p[21]; // pana la 20 de numere prime
int k;
long long N;

int main()
{
    fin >> N >> k;
    for (int i = 0; i < k; i++)
        fin >> p[i];

    long long rez = 0;

    // Iteram prin toate submultimile nevide (mask = 1..2^k - 1)
    for (int mask = 1; mask < (1 << k); mask++) {
        long long produs = 1;
        int nrBiti = 0;
        bool overflow = false;

        for (int i = 0; i < k; i++) {
            if (mask & (1 << i)) {
                // Verificam overflow inainte sa inmultim
                if (produs > N / p[i]) { overflow = true; break; }
                produs *= p[i];
                nrBiti++;
            }
        }

        if (overflow || produs > N) continue;

        if (nrBiti & 1)
            rez += N / produs; // semn pozitiv pentru submultimi de dimensiune impara
        else
            rez -= N / produs; // semn negativ pentru pare
    }

    fout << rez;
    return 0;
}

date.in:

30 3
2 3 5

date.out:

22

Pas cu pas: N=30, primele {2, 3, 5}

Iterăm prin toate cele 2^3 - 1 = 7 submulțimi nevide:

Total: 15 + 10 - 5 + 6 - 3 - 2 + 1 = 22 ✓

Vizualizare: elementele acoperite

Să vedem concret ce acoperă fiecare mulțime în [1..30]:

A (div 2): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30
B (div 3): 3, 6, 9, 12, 15, 18, 21, 24, 27, 30
C (div 5): 5, 10, 15, 20, 25, 30

Elemente în mai multe:
- 6 în A și B
- 10 în A și C
- 12 în A și B
- 15 în B și C
- 18 în A și B
- 20 în A și C
- 24 în A și B
- 25 în C
- 30 în TOATE 3

Fără PInEx, dacă adunăm |A|+|B|+|C| = 15+10+6 = 31, dar 30 are doar 22 numere divizibile - am numărat de prea multe ori.

Aplicație: funcția lui Euler (phi)

φ(n) = câte numere de la 1 la n sunt prime cu n (cmmdc = 1).

Derivare prin PInEx

Fie n = p₁^a₁ * p₂^a₂ * ... * pₖ^aₖ descompunerea în factori primi.

Un număr x ≤ n e prim cu n ⟺ nu e divizibil cu niciun pᵢ.

Câte NU sunt prime cu n? = câte sunt divizibile cu cel puțin un pᵢ. PInEx pe A₁, ..., Aₖ unde Aᵢ = {x : pᵢ | x}.

Aplicând PInEx și simplificând:

φ(n) = n - |A₁ ∪ ... ∪ Aₖ| = n * (1 - 1/p₁) * (1 - 1/p₂) * ... * (1 - 1/pₖ)

Cod

long long phi(long long n) {
    long long rez = n;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            rez -= rez / p;
        }
    }
    if (n > 1) rez -= rez / n;
    return rez;
}

Exemplu: φ(30) = 30 * (1 - 1/2) * (1 - 1/3) * (1 - 1/5) = 30 * 1/2 * 2/3 * 4/5 = 8.

Într-adevăr, numerele din {1,…,30} prime cu 30 sunt: 1, 7, 11, 13, 17, 19, 23, 29 → 8 numere ✓

Aplicație: numere coprime cu N

Câte numere de la 1 la L sunt coprime cu N (cmmdc = 1)?

Ideea

Fie p₁, p₂, ..., pₖ factorii primi distincți ai lui N.

x e coprim cu N ⟺ niciunul dintre pᵢ nu divide x.

Câte sunt coprime cu N = L - |divizibile cu cel puțin un pᵢ|

Cu PInEx pe factorii primi ai lui N.

long long coprime(long long L, long long N) {
    vector<long long> primes;
    long long n = N;
    for (long long p = 2; p * p <= n; p++)
        if (n % p == 0) {
            primes.push_back(p);
            while (n % p == 0) n /= p;
        }
    if (n > 1) primes.push_back(n);

    int k = primes.size();
    long long rez = 0;
    for (int mask = 0; mask < (1 << k); mask++) {
        long long produs = 1;
        int bits = __builtin_popcount(mask);
        for (int i = 0; i < k; i++)
            if (mask & (1 << i))
                produs *= primes[i];
        if (bits & 1) rez -= L / produs;
        else rez += L / produs;
    }
    return rez;
}

Aici pornim cu mask = 0 (mulțimea vidă, produs = 1, contribuie +L) și alternăm semnul.

Când să folosești PInEx

Semne că problema cere PInEx:

1. “Cel puțin una dintre condiții”

“Câte numere au cel puțin un divizor din {2, 3, 5}?” → PInEx.

3. Suprapunere între mulțimi

Dacă ai de numărat elemente care satisfac o condiție, dar condiția se poate “suprapune”, PInEx elimină dublele numărări.

4. Număr mic de mulțimi (k ≤ 20)

Complexitatea e O(2^k * k). Pentru k > 20 devine prea lent - ai nevoie de altă abordare.

5. Complementul e mai ușor

Uneori “cel puțin” e greu direct, dar “niciuna” e ușor (sau invers). PInEx convertește între ele.

Complexitate

Pentru k > 25, caută:

• Simplificare a structurii (poate unele intersecții sunt egale)
• Algoritm diferit (funcție Möbius, programare dinamică)

Greșeli frecvente

1. Confuzia semnului

Pentru uniune (cel puțin una):

if (nrBiti & 1)
    rez += N / produs;  // + pentru impar
else
    rez -= N / produs;  // - pentru par

Semnul e (-1)^(k+1) unde k = nr biți:

• k=1 → +
• k=2 → -
• k=3 → +
• …

Pentru complement (niciuna), începe cu mulțimea vidă și inversează: k=0 → +, k=1 → -, etc.

2. Overflow la produs

long long produs = 1;
for (...) {
    produs *= p[i]; // poate depasi long long!
    if (produs > N) break;
}

Mai bine:

if (produs > N / p[i]) { overflow = true; break; }
produs *= p[i];

Asta verifică overflow-ul înainte să înmulțim.

3. Uitarea mulțimii vide pentru complement

Pentru niciuna dintre condiții, trebuie să includem și mask = 0:

for (int mask = 0; mask < (1 << k); mask++) {
    // mask = 0 → universul intreg, semn +
}

Pentru cel puțin una, pornim de la mask = 1:

for (int mask = 1; mask < (1 << k); mask++) { ... }

4. Confuzia += cu -=

Scrie un comentariu sau folosește sgn:

int sgn = (nrBiti & 1) ? 1 : -1;
rez += sgn * (N / produs);

Mai puține bug-uri.

5. Ignorarea primelor duplicate

Pentru problema cu divizibili, primele trebuie să fie distincte (altfel intersecția nu e produsul).

Dacă ai numere oarecare (nu prime), folosește cmmmc (LCM) în loc de produs:

lcm(a, b) = a * b / gcd(a, b)

Recapitulare diagramă

                    ┌─────────────────────────┐
                    │   Problemă combinatorială  │
                    │  "câte elemente au..."    │
                    └──────────┬──────────────┘
                               │
                  ┌────────────┴────────────┐
                  │                         │
           "cel puțin una"            "niciuna"
                  │                         │
         ┌────────┴────────┐       ┌────────┴────────┐
         │ PInEx direct    │       │ PInEx pe        │
         │ mask = 1..2^k-1 │       │ complement      │
         │ semn (-1)^(k+1) │       │ mask = 0..2^k-1 │
         │                 │       │ semn (-1)^k     │
         └─────────────────┘       └─────────────────┘

Ce să reții

• PInEx numără elementele care satisfac cel puțin una dintre condițiile date.
• Formula: |A₁ ∪ ... ∪ Aₙ| = Σ (-1)^(|S|+1) * |∩S| peste submulțimi nevide.
• Semnul alternează: +, -, +, -, …
• Implementare cu bitmask în O(2^k * k).
• Pentru k > 20-25, caută altă metodă.
• Aplicații clasice:
  • Numere divizibile cu cel puțin un prim → PInEx direct
  • Funcția lui Euler φ(n) → PInEx pe factorii primi
  • Derangements D(n) = n! * Σ(-1)^j/j!
  • Funcții surjective
  • Numere coprime cu N
• Fii atent la overflow, semn și includerea/excluderea mulțimii vide.
• PInEx e fundament pentru funcția Möbius (generalizare).