Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-01-03 08:49:09.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	pinex.in, pinex.out	Sursă	Arhiva Educationala
Autor	Arhiva Educationala	Adăugată de	Serban Andrei Stan •savim
Timp execuţie pe test	1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Principiul includerii si excluderii

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.

Principiul enunţă faptul că fiind date N multimi finite A₁,A₂,A₃...A_n, relaţia de mai jos este adevărată.

$\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}|$

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 $|A \cup B|=|A|+|B|$ . 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 $|A \cap B|$ . Rezultă $|A \cup B|=|A|+|B|-|A \cap B|$ .

În diagrama din dreapta este reprezentat cazul cu trei muţimi A, B şi C. Relaţia de mai sus se extinde la $|A \cup B \cup C|=|A|+|B|+|C|-|A \cap B|-|B \cap C|-|C \cap A|+|A \cap B \cap C|$ .

Pentru cazul general, având N mulţimi A₁,A₂,A₃...A_n, vom presupune că există un element x din
$\displaystyle \bigcup_{i=1}^{n} A_{i}$ 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 $\displaystyle \bigcup_{i=1}^{k} A_{i}=C(n,1)-C(n,2)+C(n,3)+...+(-1)^{k-1} C(n,n)=1$ Rezultă relaţia de demonstrat este adevărată.

Pentru o demonstratie mai riguroasă puteţi citi de pe wikipedia sau de pe cut-the-knot.

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 mai mici ca A şi prime cu B ”. Două numere naturale (x,y) sunt prime între daca cmmdc(x,y)=1.

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₁,D₂...D_k. Este evident ca orice număr natural x care are cmmdc(x,A)≠1 va fi divizibil cu unul din numerele D₁,D₂...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.

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

Date de ieşire

Fişierul de ieşire pinex.out va conţine M linii, pe linia i fiind răspunsul la a i-a întrebare.

Restricţii

1 ≤ M ≤ 500
1 ≤ A ≤ 10¹⁸
1 ≤ B ≤ 10¹²
Pentru 30% din teste M ≤ 100, A,B ≤ 1 000
Pentru 70% din teste A,B ≤ 10⁹

Exemplu

pinex.in	pinex.out
3 10 5 20 6 50 30	8 7 14

Indicaţii de rezolvare

Vom calcula numărul de numere mai mici ca A neprime cu B. Fie D₁,D₂...D_k divizorii primi ai lui B. Fiecare astfel de divizor va determina o mulţime de numere $A_{i} = \{ x \mid x \vdots D_{i}, x \le A \}$ . Astfel, solţia va fi $A - | A_{1} \cup A_{2} \cup A_{3} ... \cup A_{k} |$ . Ş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.

Să exemplificăm pentru A=50 şi B=30. Divizorii primi ai lui B sunt 2,3 şi 5, rezultă mulţimile $A_{1}=\{2,4,6...50\}, A_{2}=\{3,6,9...48\}$ şi $A_{3}=\{5,10,15...50\}$ . 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≤k, atunci $|A_{i} \cap A_{j}| = [A / (D_{i} * D_{J})]$ . Putem extinde acestă relaţie la N mulţimi.

Astfel, pentru exemplul (50,30) avem relaţia $|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}| =$
$= [50/2] + [50/3] + [50/5] - [50/6] - [50/15] - [50/10] + [50/30] =$
$= 25 + 16 + 10 - 8 - 3 - 5 + 1 = 36$
Soluţia în acest caz va fi $50 - 36 = 14$ , cele 14 numere fiind $\{ 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49 \}$

	$A$	$B$	$C$	$A \cap B$	$A \cap C$	$B \cap C$	$A \cap B \cap C$
$1$
$2$	$\star$
$3$		$\star$
$4$	$\star$
$5$			$\star$
$6$	$\star$	$\star$		$\star$
$7$
$8$	$\star$
$9$		$\star$
$10$	$\star$		$\star$		$\star$
$11$
$12$	$\star$	$\star$		$\star$
$13$
$14$	$\star$
$15$		$\star$	$\star$			$\star$
$16$	$\star$
$17$
$18$	$\star$	$\star$		$\star$
$19$
$20$	$\star$		$\star$		$\star$
$21$		$\star$
$22$	$\star$
$23$
$24$	$\star$	$\star$		$\star$
$25$			$\star$
$26$	$\star$
$27$		$\star$
$28$	$\star$
$29$
$30$	$\star$	$\star$	$\star$	$\star$	$\star$	$\star$	$\star$
$31$
$32$	$\star$
$33$		$\star$
$34$	$\star$
$35$			$\star$
$36$	$\star$	$\star$		$\star$
$37$
$38$	$\star$
$39$		$\star$
$40$	$\star$		$\star$		$\star$
$41$
$42$	$\star$	$\star$		$\star$
$43$
$44$	$\star$
$45$		$\star$	$\star$			$\star$
$46$	$\star$
$47$
$48$	$\star$	$\star$		$\star$
$49$
$50$	$\star$		$\star$		$\star$

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 are complexitate O(M*A*log_B);

Pentru 70 puncte trebuie aplicat principiul includerii si excluderii descris mai sus. O sursă pe această idee puteţi găsi aici.

Optimizarea ce permite obţinerea punctajului maxim presupune precalcularea tuturor numerelor prime mai mici ca 10⁶. Astfel, atunci când determinăm divizorii primi ai lui B vom itera doar prin numere prime. Complexitatea acestei soluţii este O(10⁶*log_10⁶+M*sqrt(B)*2^NrDivB*NrDivB), unde prin NrDivB ne referim la numărul divizorilor primi ai lui B.

Aplicaţii

Reuniune
Suman
Mins
Pairs
Coin Changing Again, uva
Prime Frog, uva
Jap
Secventa farey
Cowfood
Rifleman sgu
Sweets, CEOI 2004

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

infoarena informatica de performanta