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ă. Tabelul de mai jos ilustrează cele spuse până acum, o casută $(p,q)$ fiind marcată daca $p$ divide $q$.

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+Nr6$, 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ă. Tabelul de mai jos ilustrează cele spuse până acum, o casută $(p,q)$ fiind marcată dacă $p$ divide $q$.

!problema/pinex?tabel.JPG 90%!
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$.