fbpx

Problema #2384 – Divigrup – Rezolvari PBInfo

de Mihai-Alexandru

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

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.

#include <bits/stdc++.h>
using namespace std;
ifstream cin("divigrup.in");
ofstream cout("divigrup.out");
int f[400];
int nrdiv(int n)
{
    int d = 2 , prod = 1;
    while(n > 1)
    {
        int p = 0;
        while(n % d == 0) p++ , n/=d;
        if(p) prod *= (p+1);
        d++;
        if(d * d > n) d = n;
    }
    return prod;
}
int main()
{
    int n , c = 0 , a[300] , v[300];
    cin >> n;
    for(int i = 0 ; i < n ; ++i)
        cin >> a[i];
    for(int i = 0 ; i < n ; i++)
        for(int j = i + 1 ; j < n ; j++)
            if(a[i] > a[j]) swap(a[i] , a[j]);
    for(int i = 0 ; i < n ; ++i)
    {
        v[i]=nrdiv(a[i]);
        if(f[v[i]]==0) c++;
        f[v[i]]++;
    }
    cout << c << '\n';
    for(int i = 300 ; i >= 1 ; --i)
    {
        int cnt = 0;
        for(int j = 0 ; j < n ; ++j)
            if(v[j]==i) cnt++;
        if(cnt  > 0)
        {
            cout << cnt << ' ';
            for(int j = 0 ; j < n ; ++j)
                if(v[j]==i)
                    cout << a[j] << ' ';
            cout << '\n';
        }
    }
    return 0;
}
Comentarii

S-ar putea sa iti placa