# PBinfo #4092 – cate – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Se dă n un număr natural și n perechi de numere (a, b).

Cerința
Să se determine:


Câte numere din intervalul închis determinat de a și b au număr impar de divizori pozitivi.
Câte numere cu exact trei divizori pozitivi se găsesc în intervalul închis determinat de a și b.

Date de intrare
Fișierul de intrare cate.in conține pe prima linie două numere naturale C și n, separate printr-un spațiu. C reprezintă cerința care trebuie rezolvată (1 sau 2), iar n reprezintă numărul de perechi. Pe următoarele n linii se găsesc cele  n perechi de numere naturale, separate prin câte un spațiu.

Date de ieșire
Fișierul de ieșire cate.out va conține n linii. Pe linia i trebuie să se găsească răspunsul la întrebarea corespunzătoare de pe linia i+1 a fișierului de intrare.

Restricții și precizări

1 ≤ n ≤ 100.000
1 ≤ a, b ≤ 1.000.000
Pentru 42 de puncte, C = 1
Pentru 58 de puncte, C = 2

Exemplul 1:
cate.in

1 3
1 10
30 10
100 500
cate.out

3
2
13
Explicație
În intervalul [1, 10] sunt 3 numere cu număr impar de divizori: 1, 4, 9.
În intervalul [10, 30] sunt 2 numere cu număr impar de divizori: 16, 25.
În intervalul [100, 500] sunt 13 numere cu număr impar de divizori.

Exemplul 2:
cate.in

2 3
1 10
30 10
100 500
cate.out

2
1
4
Explicație
În intervalul [1, 10] sunt 2 numere cu exact 3 divizori: 4, 9.
În intervalul [10, 30] este doar un număr cu exact 3 divizori: 25.
În intervalul [100, 500] sunt 4 numere cu exact 3 divizori.

## Cod sursă C++

```cpp
/* 
Raluca Costineanu 
cerinta 1 n * (nr patrate perfecte) 
cerinta 2 ciur (pt 1000) cu sume partiale 
*/
#include <bits/stdc++.h> 
using namespace std; 
ifstream f("cate.in"); 
ofstream g("cate.out"); 
int prime[1010]; 
int n, C, a, b; 
int main() 
{ 
    f>>C>>n; 
    if(C==1) 
    { 
        int x, ra, rb; 
        for(int i=1; i<=n; ++i) 
        { 
            f>>a>>b; 
            if(a>b) 
                x=a, a=b, b=x; 
            ra=sqrt(a); 
            rb=sqrt(b); 
            if(ra*ra<a) ra++; 
            g<<rb-ra+1<<'\n'; 
        } 
    } 
    else
    { 
        int i, j, x, ra, rb; 
        for(i=2; i<=1000; ++i) 
            prime[i]=1; 
        for(i=2; i<=31; ++i) 
            for(j=i*i; j<=1000; j += i) 
                prime[j]=0; 
        for(i=1; i<=1000; ++i) 
            prime[i]+=prime[i-1]; 
        for(int i=1; i<=n; ++i) 
        { 
            f>>a>>b; 
            if(a>b) 
                x=a, a=b, b=x; 
            ra=sqrt(a); 
            rb=sqrt(b); 
            if(ra*ra<a) ra++; 
            g<<prime[rb]-prime[ra-1]<<'\n'; 
        } 
    } 
    return 0; 
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4092)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4092/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4092/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)