Fişierul intrare/ieşire:pinex.in, pinex.outSursăArhiva Educationala
AutorArhiva EducationalaAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Principiul includerii si excluderii

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 mulţimi finite A1,A2,A3...An, 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|. 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 |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 A1,A2,A3...An, vom presupune că există un element x din
 \displaystyle \bigcup_{i=1}^{n} A_{i} comun pentru exact k multimi. Fie acestea Ai1, Ai2, Ai3 ... Aik. 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 i1, i2 ... ik, această intersecţie va fi evident vidă. Numărul de intersecţii a două mulţimi din cele k este  \dbinom{k}{2} , numărul de intersecţii a trei mulţimi este  \dbinom{k}{3} , etc. Cum urmărim doar elementul x, avem relaţia  \displaystyle |\bigcup_{j=1}^{k} A_{i_{j}}|=\binom{k}{1}-\binom{k}{2}+\binom{k}{3}-...+(-1)^{k-1} \binom{k}{k}=1. Rezultă că relaţia de demonstrat este adevărată.

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

Notaţii

Î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 d1, d2 ... dk. Este evident că orice număr natural x pentru care cmmdc(x, B) ≠ 1 va fi divizibil cu unul din numerele d1, d2 ... dk. 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.

Date de intrare

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

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 ≤ 1018.
  • 1 ≤ B ≤ 1012.
  • Pentru 30% din teste M ≤ 100 şi A, B ≤ 1 000.
  • Pentru 70% din teste A, B ≤ 109.

Exemplu

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

Indicaţii de rezolvare

Demonstraţii mai riguroase a acestui principiu puteţi citi pe wikipedia sau pe cut-the-knot.

În rezolvarea aplicaţiei, vom calcula numărul de numere mai mici ca A neprime cu B. Fie d1, d2 ... dk 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, soluţia va fi  A - | A_{1} \cup A_{2} \cup A_{3} \ldots \cup A_{k} | . Ş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  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 Ai şi Aj, i, j ≤ k, atunci  |A_{i} \cap A_{j}| = [A / (D_{i} * D_{j})] . Acestă relaţie se extinde natural la n mulţimi.

Astfel, pentru exemplul A = 50 şi B = 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 întrebare, verificându-se primalitatea lor cu B.

Pentru 70 puncte trebuie aplicat principiul includerii şi excluderii descris mai sus.

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

Aplicaţii

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content