Rezolvare completă PbInfo #3433 Forta

Forța unui număr natural nenul X este egală cu numărul de divizori pozitivi ai lui X. De exemplu, numărul X = 10 are forţa 4, deoarece 10 are 4 divizori, mulțimea divizorilor fiind D10 = {1,2,5,10}.

Cerința

Scrieţi un program care, cunoscând un șir de n numere naturale nenule, rezolvă următoarele cerințe:

1. determină cel mai mic număr din șir care are forța maximă;
2. determină lungimea maximă a unei secvențe formată din numere cu aceeași forţă ce poate fi obținută prin rearanjarea convenabilă a elementelor din șir.

Date de intrare

Fișierul de intrare forta.in conține pe prima linie numărul c, care reprezintă cerința de rezolvat (1 sau 2), pe a doua linie un număr natural n, iar pe următoarea linie n numere naturale separate prin câte un spațiu, reprezentând elementele șirului.

Date de ieșire

Fișierul de ieșire forta.out va conține o singură linie pe care va fi scris un număr natural reprezentând răspunsul la cerința c.

Restricții și precizări

  • 1 ≤ n ≤ 100.000
  • 1 ≤ numerele din șir ≤ 2.000.000.000
  • O secvență este constituită dintr-un singur număr sau mai multe numere aflate pe poziții consecutive în șir. Lungimea unei secvențe este egală cu numărul de valori care o compun.
  • Pentru prima cerință se acordă 50 de puncte, iar pentru cea de a doua cerință se acordă 40 de puncte.
  • Pentru teste valorând 30 de puncte 1 ≤ n ≤ 10.000
  • În concurs problema s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

Exemplul 1

forta.in

1
6
17 243 10 32 25 13

forta.out

32

Explicație

Cerința este 1. D17={1,17}, D243={1,3,9,27,81,243}, D10={1,2,5,10}, D32={1,2,4,8,16,32}, D25={1,5,25}, D13={1,13}. Deci cea mai mare forță este 6, iar numărul minim cu această forță este 32.

Exemplul 2

forta.in

2
8
121 10 14 25 49 9 25 15

forta.out

5

Explicație

Cerința este 2. O rearanjare a șirului ar putea fi (10 14 15)(121 25 49 9 25) astfel încât putem obține o secvență de lungime 3 de numere de forță 4 și o secvență de lungime 5 de numere de forță 3.

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

//Raluca Costineanu
#include <bits/stdc++.h>
using namespace std;
ifstream f("forta.in");
ofstream g("forta.out");
bool ciur[45000];
int prime[5000], cate;
void Eratostene()
{
    for(int i=3; i<=212; i+=2)
        if(ciur[i]==0)
            for(int j=i*i; j<45000; j+=i)
            ciur[j]=1;
    cate=1;
    prime[1]=2;
    for(int i=3; i<45000; i+=2)
        if(!ciur[i])prime[++cate]=i;
}
int nrDiv(int x)
{
    int k=1,p=0,i=1;
    while(i<=cate && prime[i]*prime[i]<=x)
    {
        while(x%prime[i]==0) x/=prime[i], p++;
        k*=p+1, i++, p=0;
    }
    if(x>1) k*=2;
    return k;
}
int main()
{
    Eratostene();
    int C;
    f>>C;
    if(C==1)
    {
        int n, i, x, k, pMax=0, nrMin=0;
        f>>n;
        for(i=1; i<=n; i++)
        {
            f>>x;
            k=nrDiv(x);
            if(k>pMax)pMax=k, nrMin=x;
            else if(k==pMax && x<nrMin)nrMin=x;
        }
        g<<nrMin<<'\n';
    }
    else
    {
        int nrD[1500]= {}, n, i, x, mx=0, k, maxim=0;
        f>>n;
        for(i=1; i<=n; i++)
        {
            f>>x;
            k=nrDiv(x);
            if(k>mx)mx=k;
            nrD[k]++;
        }
        for(i=1; i<=mx; i++)
            if(nrD[i]>maxim)maxim=nrD[i];
        g<<maxim<<'\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 #3433 Forta

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