h2. Indicaţii de rezolvare

*Marius* Aici zici pe larg despre soluţie şi dai un exemplu aî să ai 3 mulţimi, faci trimitere la diagramă şi analizezi cum ajungi la rezultat. După care intră textul cu modalităţi de implementare. ;) Bagă Winie!

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.
 
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.
 
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>
<tex> = [50/2] + [50/3] + [50/5]  - [50/6] - [50/15] - [50/12] + [50/30] = </tex>
<tex> = 25 + 16 + 10 - 8 - 3 - 4 + 1 = 37 </tex>
Soluţia în acest caz va fi <tex> 50 - 37 = 13</tex>, cele $13$ numere fiind <tex> \{ 1, 7, 11, 13, 17, 19, 23, 29, 37, 39, 41, 43, 47 \} </tex>

table{width: 90px; 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> | 0 | 0 | 0 | <tex> \star </tex> | 0 | 0 | 0 |

| <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 |
| <tex> 4 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 5 </tex> | 0 | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 |
| <tex> 6 </tex> | <tex> \star </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 |
| <tex> 7 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 8 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 9 </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 |
| <tex> 10 </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 |
| <tex> 11 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 12 </tex> | <tex> \star </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 |
| <tex> 13 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 14 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 15 </tex> | 0 | <tex> \star </tex> | <tex> \star </tex> | 0 | 0 | <tex> \star </tex> | 0 |
| <tex> 16 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 17 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 18 </tex> | <tex> \star </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 |
| <tex> 19 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 20 </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 |
| <tex> 21 </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 |
| <tex> 22 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 23 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 24 </tex> | <tex> \star </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 |
| <tex> 25 </tex> | 0 | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 |
| <tex> 26 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 27 </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 |
| <tex> 28 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 29 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 30 </tex> | <tex> \star </tex> | <tex> \star </tex> | <tex> \star </tex> | <tex> \star </tex> | <tex> \star </tex> | <tex> \star </tex> | <tex> \star </tex> |
| <tex> 31 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 32 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 33 </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 |
| <tex> 34 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 35 </tex> | 0 | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 |
| <tex> 36 </tex> | <tex> \star </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 |
| <tex> 37 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 38 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 39 </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 |
| <tex> 40 </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 |
| <tex> 41 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 42 </tex> | <tex> \star </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 |
| <tex> 43 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 44 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 45 </tex> | 0 | <tex> \star </tex> | <tex> \star </tex> | 0 | 0 | <tex> \star </tex> | 0 |
| <tex> 46 </tex> | <tex> \star </tex> | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 47 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 48 </tex> | <tex> \star </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 | 0 |
| <tex> 49 </tex> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <tex> 50 </tex> | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | <tex> \star </tex> | 0 | 0 |
 
Soluţia de $30$ puncte presupune parcurgerea numerelor mai mici ca $A$ la fiecare query, verificându-se primalitatea lor cu $B$. 'Această abordare':http://infoarena.ro/job_detail/372817?action=view-source are complexitate $O(M*B*log{~B~})$;
 
Pentru $70$ puncte trebuie aplicat principiul includerii si excluderii descris mai sus. O sursă pe această idee puteţi găsi 'aici':http://infoarena.ro/job_detail/372842?action=view-source.
 
Optimizarea ce permite obţinerea 'punctajului maxim':http://infoarena.ro/job_detail/372843?action=view-source reprezintă precalcularea tutror 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(M*log{~B~}*2^NrDivB^*NrDivB)$, unde prin $NrDivB$ ne referim la numărul divizorilor primi ai lui $B$.

h2. Aplicaţii