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

A gamă foarte largă de probleme în cadrul concursurilor de informatică şi nu numai se rezolvă folosind principiul includerii şi excluderii. Deşi teoria poate părea greu de înţeles, mă voi strădui să ofer o explicaţie cât mai clară pentru cei interesaţi.

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>
!>problema/pinex?Inclusion-exclusion.png 50%!

Pentru demonstraţie, vom pleca de la cazul banal când avem doar două mulţimi, fie acestea $A$ şi $B$. Dacă sunt disjuncte, este clar că reuniunea lor se calculează după relaţia <tex>|A \cup B|=|A|+|B|</tex>. Ne rămâne de rezolvat cazul când $A$ şi $B$ au cel puţin un element în comun. Relaţia anterioară numără elementele comune din cadrul reuniunii de două ori(o dată pentru $A$ şi o dată pentru $B$), de aici apare nevoia să scădem numărul acestora din rezultat. Acest lucru este uşor de făcut, dat fiind faptul că pentru $A$ şi $B$, numărul de elemente comune celor doua mulţimi este <tex>|A \cap B|</tex>. Rezultă <tex>|A \cup B|=|A|+|B|-|A \cap B|</tex>.

Pentru demonstraţie, vom pleca de la cazul banal când avem doar două mulţimi; fie acestea $A$ şi $B$. Dacă sunt disjuncte, este clar că reuniunea lor se calculează după relaţia <tex>|A \cup B|=|A|+|B|</tex>. Rămâne de rezolvat cazul când $A$ şi $B$ au cel puţin un element în comun. Relaţia anterioară numără elementele comune din cadrul reuniunii de două ori (o dată pentru $A$ şi o dată pentru $B$), de unde apare nevoia să scădem numărul acestora din rezultat. Acest lucru este uşor de făcut, dat fiind faptul că pentru $A$ şi $B$, numărul de elemente comune celor doua mulţimi este <tex>|A \cap B|</tex>. Rezultă <tex>|A \cup B|=|A|+|B|-|A \cap B|</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{~i1~},A{~i2~},A{~i3~}...A{~ik~}$. Vom considera cardinalele mulţimilor doar faţă de acest număr $x$ (cu alte cuvinte, ignormă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 $i1,i2...ik$, această intersecţie va fi evident vidă. Numărul de intersecţii a două mulţimi din cele $k$ este $C(k,2)$, numărul de intersecţii a trei mulţimi este $C(k,3)$, etc. Cum am spus ca vom urmări doar elementul $x$, avem relaţia <tex> \displaystyle \bigcup_{i=1}^{k} A_{i}=C(n,1)-C(n,2)+C(n,3)+...+(-1)^{k-1} C(n,n)=1</tex> Rezultă relaţia de demonstrat este adevărată.

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ă.

Pentru o demonstratie mai riguroasă puteţi citi de pe 'wikipedia':http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle sau de pe 'cut-the-knot':http://www.cut-the-knot.org/arithmetic/combinatorics/InclusionExclusion.shtml.

h3. Aplicaţie

h3. Aplicaţie la teoria prezentă mai sus

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$.

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 daca $cmmdc(x,y)=1$.

h3. Notaţii

h3. Care-i legătura?
 
În loc să calculăm în mod direct numărul de numere mai mici ca $A$ şi prime cu $B$, ne va fi mai uşor să calculam numărul de numere mai mici ca $A$ **neprime** cu $B$, şi apoi să scadem acest rezultat din $A$. Pentru aceasta, vom lua în considerare divizorii primi ai lui $A$, fie aceştia $D{~1~},D{~2~}...D{~k~}$. Este evident ca orice număr natural $x$ care are $cmmdc(x,A)≠1$ va fi divizibil cu unul din numerele $D{~1~},D{~2~}...D{~k~}$. De aici rezultă că o sa avem $k$ mulţimi formate din numerele naturale mai mici ca $A$ şi prime cu câte unul din divizorii primi ai lui $B$ - valoarea căutată este reprezentată de cardinalul reuniunii lor. Calcularea acestui cardinal implică principiul includerii şi exlcuderii. Pentru mai multe detalii citiţi indicaţiile de rezolvare.

În loc să calculăm în mod direct numărul de numere mai mici ca $A$ şi prime cu $B$, va fi mai uşor să calculăm numărul de numere mai mici ca $A$ şi **neprime** cu $B$, după care să scădem acest rezultat din $A$. Astfel, vom lua în considerare divizorii primi ai lui $B$; fie aceştia $d{~1~}$, $d{~2~}$ ... $d{~k~}$. Este evident că orice număr natural $x$ pentru care $cmmdc(x, B) ≠ 1$ va fi divizibil cu unul din numerele $d{~1~}$, $d{~2~}$ ... $d{~k~}$. De aici rezultă că vom avea $k$ mulţimi formate din numerele naturale mai mici ca $A$ şi prime cu câte unul din divizorii primi ai lui $B$. Valoarea căutată este reprezentată de cardinalul reuniunii lor. Calcularea acestui cardinal implică principiul includerii şi exlcuderii.

h2. Date de intrare

Fişierul de intrare $pinex.in$ va conţine pe prima linie numărul $M$, reprezentând numărul de query-uri. Următoarele $M$ linii vor conţine câte două numere $A$ si $B$, cu semnificaţia din enunţ.

Fişierul de intrare $pinex.in$ va conţine pe prima linie numărul $M$, reprezentând numărul de întrebări. Următoarele $M$ linii vor conţine câte două numere $A$ şi $B$ cu semnificaţia din enunţ.

h2. Date de ieşire

h2. Restricţii

* $1 ≤ M ≤ 500$
* $1 ≤ A ≤ 10^18^$
* $1 ≤ B ≤ 10^12^$
* Pentru $30%$ din teste $M ≤ 100, A,B ≤ 1 000$
* Pentru $70%$ din teste $A,B ≤ 10^9^$

* $1 ≤ M ≤ 500$.
* $1 ≤ A ≤ 10^18^$.
* $1 ≤ B ≤ 10^12^$.
* Pentru $30%$ din teste $M ≤ 100$ şi $A, B ≤ 1 000$.
* Pentru $70%$ din teste $A, B ≤ 10^9^$.

h2. Exemplu

h2. Indicaţii de rezolvare

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, solţia va fi <tex> A - | A_{1} \cup A_{2} \cup A_{3} ... \cup A_{k} | </tex>. Ştiind cardinalul fiecărei configuraţii de intersecţie între cele $k$ mulţimi, vom putea folosi principiul includerii si excluderii pentru calcularea numărului căutat.

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.

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.

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 $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.

Pentru o mai bună inţelegere a procesului, aplicăm relaţia pentru trei mulţimi <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: 150px; 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> |

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> |

| <tex> 1 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 2 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 3 </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 |

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