Cerința

Un șir de numere aparțin unui divigrup dacă au același număr de divizori. Scrieți un program care citește un număr natural N și apoi N numere naturale nenule și care determină:

a. câte divigrupuri există în șirul de numere citite
b. numărul de numere din fiecare divigrup, urmat de numerele ce aparțin acestuia, în ordine crescătoare.

Date de intrare

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

Date de ieșire

Fișierul de ieșire divigrup.out va conține pe prima linie numărul K, reprezentând numărul de divigrupuri ce se pot forma cu numerele de pe a doua linie a fișierului de intrare.
Pe următoarele K rânduri se vor descrie divigrupurile în ordine descrescătoare a numărului de divizori ai elementelor ce le aparțin, astfel încât fiecare rând va avea următoarea structură: M – numărul de elemente ale divigrupului – x₁ x₂ x₃ … x_M – numerele aparținând divigrupului, în ordine crescătoare. Valorile scrise pe un rând vor fi separate prin câte un spațiu.

Restricții și precizări

1 ≤ n ≤ 200
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1000000000

Exemplu

divigrup.in

11
21 99 15 9 24 100 45 28 44 4 36

divigrup.out

5
2 36 100
1 24
4 28 44 45 99
2 15 21
2 4 9

Explicație

Există 5 divigrupuri care sunt descrise pe următoarele 5 rânduri: primul divigrup format din 36 și 100, care au același număr maxim de divizori, următorul divigrup are un singur element, pe 24 care are 8 divizori, al treilea divigrup format din 28, 44, 45 și 99 are 4 elemente, toate având 6 divizori, șamd.

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 Divigrup:

#include <iostream>
#include <fstream>

using namespace std;
ifstream f("divigrup.in");
ofstream g("divigrup.out");
int a[201], divi[201], i, j, k, n, x, d, p, aux;
int main()
{
    f >> n;
    for (i = 1; i <= n; i++)
    {
        f >> a[i];
        //se determină numărul de divizori folosind descompunerea în factori primi
        x = a[i];
        d = 2;
        p = 1;
        while (d * d <=x )
        {
            k = 0;
            while (x % d == 0)
            {
                k++;
                x /= d;
            }
            if (k) p *= (k + 1);
            d++;
        }
        if (x != 1) p *= 2;
        divi[i] = p;//se reține numărul de divizori pentru fiecare valoare citită
    }
    //se ordonează vectorul descrescător după numărul de divizori și la număr de divizori egali, crescător după valoare
    for (i = 1; i <= n-1; i++)
        for (j = i+1; j <= n; j++)
            if (divi[i] < divi[j])
            {
                aux = a[i];
                a[i] = a[j];
                a[j] = aux;
                aux = divi[i];
                divi[i] = divi[j];
                divi[j] = aux;
            }
            else if (divi[i] == divi[j] && a[i] > a[j])
                {
                    aux = a[i];
                    a[i] = a[j];
                    a[j] = aux;
                }
    //se numără câte divigrupuri există
    k = 0;
    for (i = 2; i <= n; i++)
        if (divi[i] != divi[i-1])
        k++;
    g << k+1 << '\n';
    //se identifică și apoi afișează fiecare divigrup, precedat de numărul de elemente ce-l compun
    i = 1;
    while (i <= n-1)
    {
        j = i + 1;
        while (divi[j] == divi[i] && j <= n)
            j++;
        if (j - i == 0 && i == n) g << 1 << ' ' << a[n];
         else {
                g << j-i << ' ';
                for (k = i; k <= j-1; k++)
                        g << a[k] << ' ';
                }
        i = j;
        g << '\n';
    }
    //cazul particular, când printre numerele citite se găsește o singură dată valoarea 1, care are un singur divizor
    if (j - i == 0 && i == n) g << 1 << ' ' << a[n];
    return 0;
}

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 #2384 Divigrup

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2384 Divigrup 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 #2384 Divigrup