== include(page="template/taskheader" task_id="pinex") ==

A gamă foarte largă de probleme în cadrul concursurilor de informatică şi nu numai se rezolvă folosind principiul includerii şi excluderii. Deşi 'teoria':http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle poate părea greu de înţeles, mă voi strădui să ofer o explicaţie cât mai clară pentru cei interesaţi.

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{~1~},A{~2~},A{~3~}...A{~n~}$, relaţia de mai jos este adevărată.

h3. Care-i legătura?

*Marius* Zici ce reprezintă mulţimea Ai şi ce reprezintă astfel mulţimea reuniuii lor.

Î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{~1~},D{~2~}...D{~k~}$. Este evident ca orice număr natural $x$ care are $cmmdc(x,A)≠1$ va fi divizibil cu unul din numerele $D{~1~},D{~2~}...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.

h2. Date de intrare