Pagini recente » Monitorul de evaluare | Istoria paginii algoritmiada-2010/comisie | Catalysts Coding Contest 2017 Bucuresti | Diferente pentru runda/algoritmiadamirror2022runda1 intre reviziile 2 si 3 | Principiul includerii si excluderii

Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-12-23 18:12:38.
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|$

To be continued...

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.

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

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