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

Demonstraţii mai riguroase a acestui principiu puteţi citi pe 'wikipedia':http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle sau pe 'cut-the-knot':http://www.cut-the-knot.org/arithmetic/combinatorics/InclusionExclusion.shtml.

În rezolvarea aplicaţiei, vom calcula numărul de numere mai mici ca $A$ neprime cu $B$. Fie $d{~1~}$, $d{~2~}$ ... $d{~k~}$ divizorii primi ai lui $B$. Fiecare astfel de divizor va determina o mulţime de numere <tex> A_{i} = \{ x \mid x \vdots D_{i}, x \le A \} </tex>. Astfel, soluţia va fi <tex> A - | A_{1} \cup A_{2} \cup A_{3} \ldots \cup A_{k} | </tex>. Ştiind cardinalul fiecărei configuraţii de intersecţie între cele $k$ mulţimi, vom putea folosi principiul includerii şi excluderii pentru calcularea numărului căutat.

În rezolvarea aplicaţiei, vom calcula numărul de numere mai mici ca $A$ neprime cu $B$. Fie $d{~1~}$, $d{~2~}$ ... $d{~k~}$ divizorii primi ai lui $B$. Fiecare astfel de divizor va determina o mulţime de numere <tex> A_{i} = \{ x \mid x \vdots d_{i}, x \le A \} </tex>. Astfel, soluţia va fi <tex> A - | A_{1} \cup A_{2} \cup A_{3} \ldots \cup A_{k} | </tex>. Ştiind cardinalul fiecărei configuraţii de intersecţie între cele $k$ mulţimi, vom putea folosi principiul includerii şi excluderii pentru calcularea numărului căutat.

Să exemplificăm pentru $A = 50$ şi $B = 30$. Divizorii primi ai lui $B$ sunt $2$, $3$ şi $5$. Rezultă mulţimile <tex> A_{1}=\{2,4,6...50\}, A_{2}=\{3,6,9...48\} </tex> şi <tex> A_{3}=\{5,10,15...50\} </tex>. Tabelul de mai jos ilustrează toate cele $7$ mulţimi care vor apărea în operaţiile efectuate de noi, precum şi elementele conţinute de acestea.

Numărul de numere mai mici ca $A$ şi divizibile cu $x$ va fi $[A/x]$ (parte întreagă din $A$ împărţit la $x$). De asemenea, dacă avem două mulţimi $A{~i~}$ şi $A{~j~}$, $i, j &le; k$, atunci <tex> |A_{i} \cap A_{j}| = [A / (D_{i} * D_{J})] </tex>. Putem extinde acestă relaţie la $n$ mulţimi.

Numărul de numere mai mici ca $A$ şi divizibile cu $x$ va fi $[A/x]$ (parte întreagă din $A$ împărţit la $x$). De asemenea, dacă avem două mulţimi $A{~i~}$ şi $A{~j~}$, $i, j &le; k$, atunci <tex> |A_{i} \cap A_{j}| = [A / (D_{i} * D_{j})] </tex>. Acestă relaţie se extinde natural la $n$ mulţimi.

Astfel, pentru exemplul $A = 50$ şi $B = 30$, avem relaţia <tex> |A_{1} \cup A_{2} \cup A_{3}|=|A_{1}|+|A_{2}|+|A_{3}|-|A_{1} \cap A_{2}|-|A_{2} \cap A_{3}|-|A_{3} \cap A_{1}|+|A_{1} \cap A_{2} \cap A_{3}| = </tex>

Astfel, pentru exemplul $A = 50$ şi $B = 30$, avem relaţia...
 
<tex> |A_{1} \cup A_{2} \cup A_{3}|=|A_{1}|+|A_{2}|+|A_{3}|-|A_{1} \cap A_{2}|-|A_{2} \cap A_{3}|-|A_{3} \cap A_{1}|+|A_{1} \cap A_{2} \cap A_{3}| = </tex>

<tex> = [50/2] + [50/3] + [50/5]  - [50/6] - [50/15] - [50/10] + [50/30] = </tex>
<tex> = 25 + 16 + 10 - 8 - 3 - 5 + 1 = 36 </tex>

Soluţia în acest caz va fi <tex> 50 - 36 = 14 </tex>, cele $14$ numere fiind <tex> \{ 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49 \} </tex>
table{width: 900px; text-align: center}. | | <tex> A </tex> | <tex> B </tex> | <tex> C </tex>| <tex> A \cap B </tex> | <tex> A \cap C </tex> | <tex> B \cap C </tex> | <tex> A \cap B \cap C </tex> |

h3. Detalii de implementare

Soluţia de $30$ puncte presupune parcurgerea numerelor mai mici ca $A$ la fiecare query, verificându-se primalitatea lor cu $B$. 'Această abordare':job_detail/372817?action=view-source are complexitate $O(M*A*log{~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 trebuie aplicat principiul includerii si excluderii descris mai sus. O sursă pe această idee puteţi găsi 'aici':job_detail/372842?action=view-source.

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

Optimizarea ce permite obţinerea 'punctajului maxim':job_detail/379646?action=view-source presupune precalcularea tuturor numerelor prime mai mici ca $10^6^$. Astfel, atunci când determinăm divizorii primi ai lui $B$ vom itera doar prin numere prime. Complexitatea acestei soluţii este $O(10^6^*log{~10^6^~}+M*sqrt(B)*2^NrDivB^*NrDivB)$, unde prin $NrDivB$ ne referim la numărul divizorilor primi ai lui $B$.

Optimizarea ce permite obţinerea punctajului maxim presupune precalcularea tuturor numerelor prime mai mici ca $10^6^$. Astfel, atunci când determinăm divizorii primi ai lui $B$ vom itera doar prin numere prime. Complexitatea acestei 'soluţii':job_detail/379646?action=view-source este <tex> O(M*\sqrt{B}*2^X*X) </tex>, unde prin $X$ ne referim la numărul divizorilor primi ai lui $B$.

h2. Aplicaţii

'Reuniune':problema/reuniune
'Suman':problema/suman
'Mins':problema/mins
'Pairs':problema/pairs
"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
'Jap':problema/jap
'Secventa farey':problema/farey
'Cowfood':problema/cowfood
'Rifleman':http://acm.sgu.ru/problem.php?contest=0&problem=370 sgu
"Sweets":http://www.oi.edu.pl/ceoi2004/problems/swe.pdf, CEOI 2004

* 'Frac':problema/frac
* 'Reuniune':problema/reuniune
* 'Suman':problema/suman
* '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_
* 'Sweets':http://www.oi.edu.pl/ceoi2004/problems/swe.pdf, _CEOI, 2004_

== include(page="template/taskfooter" task_id="pinex") ==

4407