Cerința

Se dă un șir de n numere naturale nenule v = {v₁ , v₂ , v₃ ... v_n }.

Se formează șirul d = {d₁ , d₂ , d₃ ... d_n } unde d_i = numărul divizorilor lui v_i .

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 v_i apare de mai multe ori în șirul v și numărul divizorilor lui v_i este egal cu max, atunci v_i 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ă.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema masterpiece001:

//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<<' ';
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2366 masterpiece001

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2366 masterpiece001 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2366 masterpiece001