pinex

Principiul includerii si excluderii

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

Poveste şi cerinţă...

Trebuie să 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$.

h2. Date de intrare

Fişierul de intrare $pinex.in$ ...

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

h2. Date de ieşire

În fişierul de ieşire $pinex.out$ ...

Fişierul de ieşire $pinex.out$ va conţine $M$ linii, pe linia $i$ fiind răspunsul la a $i-a$ întrebare.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ M ≤ 1 000$
* $1 ≤ A ≤ 10^18^$
* $1 ≤ B ≤ 10^12^$
* Pentru 30% din teste $M ≤ 100, A,B ≤ 1 000$
* Pentru 70% din teste $A,B ≤ 10^9^$

h2. Exemplu
table(example). |_. pinex.in |_. pinex.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3
10 5
20 6
50 30
| 8
7
14

|

h3. Explicaţie

h2. Indicaţii de rezolvare

...

O primă soluţie are complexitate $O(M*A*log(A+B))$ şi ar obţine $30$ de puncte. În acest caz vom parcurge toate numerele din intervalul $(1,A)$, verificând pentru fiecare dacă are cmmdc-ul cu $B$ egal cu $1$. O sursă pe această idee se poate găsi aici.
 
Pentru o soluţie mai performantă trebuie implementat principiul includerii si excluderii, despre care puteţi citi pe 'wikipedia':http://en.wikipedia.org/wiki/Inclusion-exclusion_principle sau pe 'mathworld':http://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html. Concret, presupunând că trebuie să raspundem la query-ul $20 6$, o să ne intereseze numărul de numere divizibile cu $2$, numărul de numere divizibile cu $3$ şi numărul de numere divizibile cu $2 şi 3$ mai mici decât $20$. Numarul de numere divizibile cu $x$ mai mici decat $y$ va fi simplu $[y/x]$ (parte intreagă din $y/x$). Soluţia noastră va fi reprezentată de $A-Nr2-Nr3+Nr23$, unde $Nrx$ este numărul de numere divizibile cu $x$ mai mici decât $20$. Observăm ca numarul de apariţii ale numerelor cu număr impar de factori primi se scad din solţie, în timp ce pentru număr par de factori primi se adună. Această abordare are complexitate $O(T*NRMAXF*2^NRMAXF^)$ şi ar obţine $70$ de puncte. Prin $NRMAXF$ ne referim la numărul maxim de factori primi ce poate să îi aibă numărul $B$. Această implementare poate fi gasită aici.
 
Pentru obţinerea punctajului maxim trebuie să aducem nişte îmbunatăţiri soluţiei precedente. În primul rând, atunci când determinăm factorii primi ai lui $B$, ne vom uita pana la $sqrt(B)$. Cum această valoare este $≤ 1 000 000$, putem precalcula numerele prime prin care vom itera la fiecare query. Altă optimizare utilă nu doar la această problemă este să precalculăm puterile lui $2$ pentru backtracking-ul care ne determina soluţia. Soluţia de $100$ de puncte se află aici.

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