# PBinfo #3680 – numereX – Rezolvare C++

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

## Enunț

Pentru un număr natural nenul X, se numește divizor propriu al lui X, un divizor natural al lui X, diferit de 1 și X. De exemplu, pentru numărul 20 divizorii proprii sunt 2, 4, 5, 10, iar numărul 20 are 4 divizori proprii.

Cerința
1. Se dă un număr natural N. Determinați cel mai mic număr din intervalul închis [1,N] care are număr maxim de divizori proprii.
2. Se dau trei numere N, M și T. Determinați câte intervale de forma [a,b] au proprietatea că există exact M numere naturale care au T divizori proprii.

Date de intrare
Fișierul de intrare numere.in conține pe prima linie un număr natural P reprezentând cerința din problemă care trebuie rezolvată.

Dacă P = 1 atunci pe a doua linie se găsește un număr natural N, reprezentând extremitatea din dreapta a intervalului.

Dacă P = 2 atunci pe a doua linie se găsesc trei numere: un număr natural N, un număr natural M și un număr natural T cu semnificațiile din enunț.

Date de ieșire
Dacă P = 1 atunci fișierul de ieșire numere.out conține pe o singură linie numărul cel mai mic determinat care are număr maxim de divizori.

Dacă P = 2 atunci fișierul de ieșire numere.out conține pe o singură linie numărul de intervale determinate care au proprietatea cerută.

Restricții și precizări

1 ≤ N ≤ 100000
1 ≤ M ≤ 100000
1 ≤ T ≤ 100000
1 ≤ a ≤ b ≤ N
Pentru rezolvarea corectă a cerinței 1 se acordă 40 de puncte, pentru rezolvarea corectă a cerinței 2 se acordă 60 de puncte.

Exemplul 1:
numere.in

1
20
numere.out

12
Explicație
12 are 4 divizori proprii și este cel mai mic număr cu 4 divizori proprii din [1,20].

Exemplul 2:
numere.in

2
10 3 2
numere.out

6
Explicație
[1,10], [2,10], [3,10], [4,10], [5,10], [6,10] sunt cele 6 intervale în care se găsesc exact 3 numere cu 2 divizori proprii(6, 8, 10 sunt numerele cu 3 divizori proprii).

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream cin ("numere.in");
ofstream cout("numere.out");
int v[100010],s[100010];
int p,n,m,t,kmax,nmax;
int nrDivPrim(int x)
{
    int d,y=0;
    for(d=2;d<=x/2; d++)
        if(x%d==0)
        y++;
    return y ;
}
int main () {
    int x,y;
    cin>>p>>n;
    if(p==2)
    {
        int k,dif;
        cin>>m>>t;
        for (int i=1;i<=n;++i)
        {
            k=nrDivPrim(i);
            if(k==t)v[i]=1;
        }
        k=0;
        for (int i=2;i<=n;++i)v[i]+=v[i-1];
        for (int i=1;i<=n;++i)
        for (int j=i+1;j<=n;++j)
            {
                if((dif=v[j]-v[i-1])==m)k++;
                else if((dif=v[j]-v[i-1])>m) j=n+1;
            }
        cout<<k;
    }
    else
    {for (int i=1;i<=n;++i)
        {
            int y=nrDivPrim(i);
            if(y>kmax){kmax=y;nmax=i;}
        }
        cout<<nmax;
    }
    return 0;
}
```

## Resurse

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