Rezolvare completă PbInfo #2905 Divizori4

Cerința

Gigel a găsit un șir cu n numere naturale, numerotate de la 1 la n și un număr p. Neavând chef de muncă, Gigel vă cere să rezolvați următoarele cerințe:

a) Aflați câți divizori are numărul din șir aflat pe poziția p.
b) Afișați în ordine descrescătoare numerele din șir care au același număr de divizori ca cel aflat pe poziția p.

Date de intrare

Fișierul de intrare divizori4.in conține pe prima linie numerele n c, unde c poate fi doar 1 sau 2. A doua linie conține cele n elemente ale șirului. A treia linie conține numărul p.

Date de ieșire

Dacă c=1 se rezolvă numai cerința a). Fișierul de ieșire divizori4.out va conține pe prima linie numărul de divizori ai numărului aflat în șir pe poziția p.

Dacă c=2 se rezolvă numai cerința b). Fișierul de ieșire divizori4.out va conține pe prima linie, în ordine descrescătoare, numerele din șir cu același număr de divizori ca și cel aflat pe poziția p.

Restricții și precizări

  • numerele din șir vor fi numere naturale nenule mai mici sau egale cu 1.000.000.000
  • pentru 50% din punctaj c=1; pentru 50% din punctaj c=2;
  • pentru c=1, 1 ≤ p ≤ n ≤ 50.000
  • pentru c=2, 1 ≤ p ≤ n ≤ 50.000 pentru 30% din punctaj și 1 ≤ p ≤ n ≤ 10.000 pentru 20% din punctaj

Exemplul 1

divizori4.in

10 1
1 5 95 23 16 39 77 74 97 57 
3

divizori4.out

4

Explicație

c=1, se rezolvă doar cerința a). Al treilea număr din șir este 95, care are 4 divizori (1 5 19 95).

Exemplul 2

divizori4.in

10 2
1 5 95 23 16 39 77 74 97 57 
3

divizori4.out

95 77 74 57 39

Explicație

c=2, se rezolvă doar cerința b). Al treilea număr din șir este 95, care are 4 divizori. Numerele cu 4 divizori din șir sunt, în ordine descrescătoare: 95 77 74 57 39.

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

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>

using namespace std;

ifstream fin("divizori4.in");
ofstream fout("divizori4.out");

int n, c, p, A[50001], e[40001], prime[40000], nrp;

int nr_div(int n)
{
    int rez = 1, p , d = 1;
    while(n > 1)
    {
        p = 0;
        while(n % prime[d] == 0)
            n /= prime[d], p ++;
        rez *= p + 1;
        d ++;
        if(prime[d] * prime[d] > n && n > 1)
            rez *= 2, n = 1;
    }
    return rez;
}



int main()
{
    e[0] = e[1] = 1;
    for(int i = 2 ; i * i <= 40000 ; i ++)
        if(e[i] == 0)
            for(int  j = 2 ; i * j <= 40000 ; j ++)
                e[i*j] = 1;
    for(int i = 2 ; i  <= 40000 ; i ++)
        if(e[i] == 0)
            prime[++nrp] = i;
    fin >> n >> c;
    assert(n <= 50000);
    for(int i = 1; i <= n ; i ++)
        fin >> A[i];
        
    fin >> p;
    int nrdx = nr_div(A[p]);
    if(c == 1)
        fout << nrdx << "
";
    else
    {
        sort(A+1, A+n+1, greater<int>());
        for(int i = 1 ; i <= n ; i ++)
            if(nr_div(A[i]) == nrdx)
                fout << A[i] << " ";
        fout << "
";
    }
    fin.close();
    fout.close();
    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 #2905 Divizori4

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