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ă.

#include <bits/stdc++.h>

using namespace std;
ifstream cin("masterpiece001.in");
ofstream cout("masterpiece001.out");
bitset<400001> a;
int nrdiv(int n)
{
    int d = 2 , cnt = 1;
    int d2=0;
    while(n%2==0) { d2++; n=n/2;}
    cnt=d2+1;
    d=3;
    while(n > 1)
    {
        int p = 0;
        while(n % d == 0){n/=d;p++;}
        cnt = cnt * (p+1);
        d=d+2;
        if(d * d > n)d = n;
    }
    return cnt;
}
int main()
{
    int n , x , ndmax=0,max = 0 ,min=400000,s=400000,d=0;
    cin >> n;
    for(int i = 0 ; i < n ; ++i)
    {
        cin >> x;
        a[x]=1;
        if(x<s) s=x;
        if(x>d) d=x;
    }
    for(int y=s;y<=d;y++)
        if(a[y])
    {
        int nd=nrdiv(y);
        if(nd>ndmax)
        {
            ndmax = nd;
            max=min=y;
        }
        else if(nd==ndmax)
                  max=y;
    }
    for(int i=min;i<=max;i++)
        if(a[i] && nrdiv(i)==ndmax)
            cout<<i<<" ";
    return 0;
}