O gamă foarte largă de probleme în cadrul concursurilor de informatică, şi nu numai, se rezolvă folosind _principiul includerii şi excluderii_. Teoria poate părea greu de înţeles, aşa că vom încerca să oferim o explicaţie cât mai clară pentru cei interesaţi.

Principiul enunţă faptul că fiind date $n$ multimi finite $A{~1~},A{~2~},A{~3~}...A{~n~}$, relaţia de mai jos este adevărată...

Principiul enunţă faptul că fiind date $n$ mulţimi finite $A{~1~},A{~2~},A{~3~}...A{~n~}$, relaţia de mai jos este adevărată...

<tex> \displaystyle | \bigcup_{i=1}^{n} A_{i} | =  \sum_{i=1}^{n} | A_{i} | - \sum_{i,j:1 \le i < j \le n} |A_{i} \cap A_{j} | + \sum_{i,j,k:1 \le i < j < k \le n} |A_{i} \cap A_{j} \cap A_{k}| - \ldots + (-1)^{n-1} |A_{1} \cap \ldots \cap A_{n}| </tex>

În diagrama din dreapta este reprezentat cazul cu trei muţimi $A$, $B$ şi $C$. Relaţia de mai sus se extinde la <tex> |A \cup B \cup C|=|A|+|B|+|C|-|A \cap B|-|B \cap C|-|C \cap A|+|A \cap B \cap C| </tex>.
Pentru cazul general, având $n$ mulţimi $A{~1~},A{~2~},A{~3~}...A{~n~}$, vom presupune că există un element $x$ din

<tex> \displaystyle \bigcup_{i=1}^{n} A_{i} </tex> comun pentru exact $k$ multimi. Fie acestea $A{~i{~1~}~}$, $A{~i{~2~}~}$, $A{~i{~3~}~}$ ... $A{~i{~k~}~}$. Vom considera cardinalele mulţimilor doar faţă de acest număr $x$ (cu alte cuvinte, ignorăm celelalte elemente). Dacă vom face intersecţia a mai mult de $k$ mulţimi, sau a unor mulţimi cu indicele de ordine diferit de $i{~1~}$, $i{~2~}$ ... $i{~k~}$, această intersecţie va fi evident vidă. Numărul de intersecţii a două mulţimi din cele $k$ este <tex> \dbinom{k}{2} </tex>, numărul de intersecţii a trei mulţimi este <tex> \dbinom{k}{3} </tex>, etc. Cum urmărim doar elementul $x$, avem relaţia <tex> \displaystyle \bigcup_{j=1}^{k} A_{i_{j}}=\binom{k}{1}-\binom{k}{2}+\binom{k}{3}-...+(-1)^{k-1} \binom{k}{k}=1</tex>. Rezultă că relaţia de demonstrat este adevărată.

<tex> \displaystyle \bigcup_{i=1}^{n} A_{i} </tex> comun pentru exact $k$ multimi. Fie acestea $A{~i{~1~}~}$, $A{~i{~2~}~}$, $A{~i{~3~}~}$ ... $A{~i{~k~}~}$. Vom considera cardinalele mulţimilor doar faţă de acest număr $x$ (cu alte cuvinte, ignorăm celelalte elemente). Dacă vom face intersecţia a mai mult de $k$ mulţimi, sau a unor mulţimi cu indicele de ordine diferit de $i{~1~}$, $i{~2~}$ ... $i{~k~}$, această intersecţie va fi evident vidă. Numărul de intersecţii a două mulţimi din cele $k$ este <tex> \dbinom{k}{2} </tex>, numărul de intersecţii a trei mulţimi este <tex> \dbinom{k}{3} </tex>, etc. Cum urmărim doar elementul $x$, avem relaţia <tex> \displaystyle |\bigcup_{j=1}^{k} A_{i_{j}}|=\binom{k}{1}-\binom{k}{2}+\binom{k}{3}-...+(-1)^{k-1} \binom{k}{k}=1</tex>. Rezultă că relaţia de demonstrat este adevărată.

h3. Aplicaţie

Răspundeţi la $M$ întrebări de tipul: „dându-se două numere naturale $A$ şi $B$, să se determine numărul de numere mai mici ca $A$ şi prime cu {$B$}”. Două numere naturale $x$, $y$ sunt prime între ele dacă ${'cmmdc':problema/euclid2}(x, y) = 1$.

Răspundeţi la $M$ întrebări de tipul: „ dându-se două numere naturale $A$ şi $B$, să se determine numărul de numere naturale mai mici sau egale cu $A$ şi prime cu {$B$} ”. Două numere naturale $x$, $y$ sunt prime între ele dacă ${'cmmdc':problema/euclid2}(x, y) = 1$.

h3. Notaţii

h3. Detalii de implementare

'Soluţia de $30$ puncte':job_detail/372817?action=view-source are complexitate <tex> O(M*A*log_{B}(A!)) </tex> şi presupune parcurgerea numerelor mai mici ca $A$ la fiecare întrebare, verificându-se primalitatea lor cu $B$.

'Soluţia de $30$ puncte':job_detail/372817?action=view-source presupune parcurgerea numerelor mai mici ca $A$ la fiecare întrebare, verificându-se primalitatea lor cu $B$.

Pentru '$70$ puncte':job_detail/372842?action=view-source trebuie aplicat principiul includerii şi excluderii descris mai sus.

* 'Mins':problema/mins
* 'Pairs':problema/pairs
* 'Jap':problema/jap

* 'Gol3d':problema/gol3d

* 'Secventa farey':problema/farey
* 'Cowfood':problema/cowfood

* 'Borg':http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=741, _ONI 2006_

* 'Coin Changing Again':http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2226, _UVA_
* 'Prime Frog':http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2291, _UVA_
* 'Rifleman':http://acm.sgu.ru/problem.php?contest=0&problem=370 _SGU_

4407