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>

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

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

| <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> 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~})$;

h3. Detalii de implementare

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.

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~})$;

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

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.
 
Optimizarea ce permite obţinerea 'punctajului maxim':job_detail/379646?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