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ă;

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 ≤ 100000
• 1 ≤ numerele din șir ≤ 2000000000
• 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 ≤ 10000
• Î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.

#include <bits/stdc++.h>

using namespace std;

ifstream cin("forta.in");
ofstream cout("forta.out");

long long n , cer , maxi , vali , cnt;
int E[100001] , P[8001];

struct poz
{
    int val , f;
}a[100001];


void ciur()
{
    long long maxi = 100001;
    for(int i = 2 ; i <= maxi ; i++) E[i] = 1;
    for(int i = 2 ; i * i <= maxi ; i++)
        if(E[i] == 1)
            for(int j = i * i; j <= maxi ; j += i) E[j] = 0;

    for(int i = 2 ; i <= maxi ; i++)
        if(E[i] == 1) P[++cnt] = i;
}

long long nrdiv(int n)
{
    long long d = 1 , prod = 1;
    while(n > 1 && P[d] * P[d] <= n)
    {
        int p = 0;
        while(n % P[d] == 0) p++ , n /= P[d];
        if(p) prod *= (p + 1);
        d++;
    }
    if(n != 1)prod *= 2;
    return prod;
}

int comp(poz a , poz b)
{
    if(a.f < b.f) return 1;
    else if(a.f == b.f && a.val < b.val) return 1;
    else return 0;
}

int main()
{
    cin >> cer >> n;
    ciur();
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i].val;
        a[i].f = nrdiv(a[i].val);
        if(a[i].f > maxi) maxi = a[i].f , vali = a[i].val;
        else if(a[i].f == maxi)
            if(a[i].val < vali) vali = a[i].val;
    }
    if(cer == 1) cout << vali;
    else
    {
        sort(a + 1 , a + n + 1 , comp);
        if(n > 1)
        {
            maxi = -10000 , cnt = 0;
            for(int i = 2 ; i <= n ; i++)
            {
                //cout << cnt << '\n';
                if(a[i].f == a[i - 1].f) cnt++;
                else
                {
                    if(cnt > maxi) maxi = cnt;
                    cnt = 0;
                }
            }
            if(cnt > 0)
                if(cnt > maxi) maxi = cnt;
            cout << maxi + 1;
        }
        else cout << 1;
    }

}