# PBinfo #2366 – masterpiece001 – Rezolvare C++

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

## Enunț

Cerința
Se dă un șir de n numere naturale nenule v = {v1 , v2 , v3  ... vn }.

Se formează șirul d = {d1 , d2 , d3  ... dn } unde di = numărul divizorilor lui vi . 

Notăm max = cea mai mare valoare din șirul d.

Să se afișeze în ordine crescătoare toate numerele din șirul dat v care au exact max divizori. Dacă un număr vi apare de mai multe ori în șirul v și numărul divizorilor lui vi este egal cu max, atunci vi se va afișa o singură dată.

Date de intrare
Fișierul de intrare masterpiece001.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale nenule separate prin spații.

Date de ieșire
Fișierul de ieșire masterpiece001.out va conține numerele din șirul dat v care au exact max divizori, în ordine crescătoare, separate prin spații.

Restricții și precizări

1 ≤ n ≤ 1.000.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici sau egale cu 400.000

Exemplu:
masterpiece001.in

10
12 3 12 4 12 18 31 101 31 31
masterpiece001.out

12 18
Explicație
12 si 18 au 6 divizori. Celelalte numere din șir au mai puțin de 6 divizori. Se observă că numărul 12 apare de două ori, cu toate acestea, se va afișa o singură dată.

## Cod sursă C++

```cpp
//100p
#include "fstream"
using namespace std;
ifstream cin("masterpiece001.in");
ofstream cout("masterpiece001.out");
char V[60010] = {};
char T[60010] = {};
int main(){
    int n, x, maxim=0, maxim_div=0;
    cin >> n;
    for(int i=1 ; i<=n ; ++i){
        cin >> x;
        if(x > maxim)
            maxim = x;
        if(!(T[x / 8] & (1 << (x % 8)))){
            T[x / 8] = T[x / 8] | (1 << (x % 8));
                int nrd=1, k=x, p=0;
                while(!(k & 1))
                    ++ p, k >>= 1;
                nrd *= p + 1;
                for(int d=3 ; d*d<=k ; d+=2){
                    p = 0;
                    while(k % d == 0)
                        ++ p, k /= d;
                    nrd *= p + 1;
                }
                if(k > 1)
                    nrd *= 2;
            if(nrd > maxim_div){
                maxim_div = nrd;
                for(int i=1 ; i<=maxim ; ++i)
                   V[i / 8] = V[i / 8] & (255 ^ (1 << (i % 8)));
                V[x / 8] = V[x / 8] | (1 << (x % 8));
            }
            else if(nrd == maxim_div)
                V[x / 8] = V[x / 8] | (1 << (x % 8));
        }
    }
    for(int i=1 ; i<=maxim ; ++i)
        if(V[i / 8] & (1 << (i % 8)))
            cout<<i<<' ';
}
```

## Resurse

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