Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | asi.in, asi.out | Sursă | FMI No Stress 9 Warmup |
| Autor | Mihai-Dragos Preda, Stefan Radu | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 32768 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Asi
Cătălin şi-a făcut, ca tot românul, provizii pentru criza ce urmează. Acesta are acum o cantitate suficientă (“fără număr”) din fiecare tip de bancnota. In Alexandria, oraşul în care locuieşte, se folosesc doar bancnote care au valoarea egală cu un număr prim. El numeşte un număr “as” dacă este o putere mai mare strict ca 1 a unei bancnote şi pune pariu pe toţi banii lui ca nu puteţi răspunde la Q întrebări de forma: "Câţi aşi sunt în intervalul [A, B]?".
Încercaţi să răspundeţi la întrebările lui Cătălin pentru a câştiga pariul.
Date de intrare
Fişierul de intrare asi.in conţine pe prima linie un număr natural Q reprezentând numărul de întrebări. Pe următoarele Q linii se găsesc câte 2 numere A şi B, reprezentând capetele intervalului din întrebarea Q.
Date de ieşire
În fişierul de ieşire asi.out se vor afla Q numere cu răspunsul, în ordine, la cele Q întrebări.
Restricţii
- 1 ≤ A ≤ B ≤ 1012
- 1 ≤ Q ≤ 105
- Cătălin de la Alexandria considera un număr "as" dacă poate fi scris ca pi unde p este prim şi i ≥ 2
- 1 nu este considerat numar prim
Precizări
- Pentru teste in valoare de 5 puncte:
- 1 ≤ A ≤ B ≤ 102
- 1 ≤ Q ≤ 103
- Pentru alte teste in valoare de 5 puncte:
- 1 ≤ A ≤ B ≤ 103
- 1 ≤ Q ≤ 103
- Pentru alte teste in valoare de 15 puncte:
- 1 ≤ A ≤ B ≤ 109
- 1 ≤ Q ≤ 103
- Pentru alte teste in valoare de 15 puncte:
- 1 ≤ A ≤ B ≤ 106
- 1 ≤ Q ≤ 105
- Pentru alte teste in valoare de 20 de puncte:
- 1 ≤ A ≤ B ≤ 109
- 1 ≤ Q ≤ 105
Exemplu
| asi.in | asi.out |
|---|---|
| 1 7 20 | 3 |
Explicaţie
Intre 7 şi 20 singurele numere care respecta regula sunt 8 = 23, 9 = 32 şi 16 = 24.
