# PBinfo #3433 – Forta – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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.

## Cod sursă C++

```cpp
//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;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3433)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3433/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3433/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)