h2. "Asi":https://infoarena.ro/problema/asi

Observam usor ca numerele cautate sunt puteri de numere prime mai mici decat 10 la puterea a 6-a (de aici restrictia ca puterea sa fie cel putin 2). Vom folosi ciurul lui Eratostene pentru a determina aceste numere prime. Pentru fiecare numar prim, vom calcula puterile sale cu valoare mai mica decat B (observam ca vom avea putine numere intrucat, cu cat creste valoarea numarului prim, cu atat scade puterea sa astfel incat sa fie mai mica decat B ). Dupa ce am introdus toate aceste puteri intr-un vector, il vom sorta. Pentru a raspunde la query-uri, observam ca numarul elementelor valide mai mici sau egale decat B minus numarul elementelor valide mai mici decat A ne ofera numarul elementelor valide intre A si B; vom folosi cautare binara pentru aceste 2 pozitii in vectorul creat anterior, iar raspunsul va fi dat de diferenta dintre cele 2 pozitii.

Observam usor ca numerele cautate sunt puteri de numere prime mai mici decat 10 la puterea a 6-a (de aici restrictia ca puterea sa fie cel putin 2). Vom folosi ciurul lui Eratostene pentru a determina aceste numere prime. Pentru fiecare numar prim, vom calcula puterile sale cu valoare mai mica decat 10^12 (observam ca vom avea putine numere intrucat, cu cat creste valoarea numarului prim, cu atat scade puterea sa astfel incat sa fie mai mica decat 10^12 ). Dupa ce am introdus toate aceste puteri intr-un vector, il vom sorta. Pentru a raspunde la query-uri, observam ca numarul elementelor valide mai mici sau egale decat B minus numarul elementelor valide mai mici decat A ne ofera numarul elementelor valide intre A si B; vom folosi cautare binara pentru aceste 2 pozitii in vectorul creat anterior, iar raspunsul va fi dat de diferenta dintre cele 2 pozitii.

h2. "Logik":https://infoarena.ro/problema/logik