Adrian este pasionat de matematică. El utilizează denumirea maxdiv pentru numărul care are cei mai mulţi divizori, dintre numerele unui şir dat. Adrian ştie că o secvenţă este un subşir de numere care apar pe poziţii consecutive într-un şir. El denumeşte secvenţă maxdiv o secvenţă din şir, formată din cel puţin două numere, ce începe şi se încheie cu un număr maxdiv şi nu conţine alte numere maxdiv în interior.

Având la dispoziţie un şir de n numere naturale, doreşte să afişeze cea mai lungă secvenţă maxdiv şi numărul de secvenţe maxdiv din şir. Dacă şirul de numere dat conţine mai multe secvenţe maxdiv de aceeaşi lungime maximă, se va afişa prima secvenţă de acest tip din şir.

Cerința

Scrieţi un program care afişează, pentru un şir dat format din n numere naturale numărul de secvenţe maxdiv şi cea mai lungă secvenţă maxdiv.

Date de intrare

Fişierul de intrare maxdiv.in conţine pe prima linie numărul n separat printr-un spaţiu de un număr natural t, care reprezintă cerinţa: 1, dacă se cere numărul de secvenţe maxdiv, respectiv 2 dacă se cere cea mai lungă secvenţă maxdiv. Linia a doua din fişier conţine cele n numere naturale ale şirului dat.

Date de ieșire

Fişierul de ieșire maxdiv.out va conţine pe prima linie un număr natural ce reprezintă numărul de secvenţe maxdiv, pentru şirul de numere dat, dacă cerinţa este 1. Dacă cerinţa este 2, fişierul de ieşire va conţine un şir de numere naturale, separate între ele prin câte un spaţiu, ce reprezintă cea mai lungă secvenţă maxdiv din şirul dat.

Restricții și precizări

• 2 ≤ n ≤ 1000
• 2 ≤ x[i] ≤ 1000000, unde x[i] reprezintă un număr din şirul dat
• Şirul de numere conţine cel puţin o secvenţă care începe şi se încheie cu un număr maxdiv
• Pentru cerința 1 se acordă 40% din punctaj, iar pentru cerința 2 se acordă 60% din punctaj.

Exemplu 1:

maxdiv.in

7 1
22 60 64 125 315 24 150

maxdiv.out

2

Explicație

Cerinţa 1: Şirul de numere dat conţine 3 numere maxdiv: 60, 315 şi 150 (au fiecare 12 divizori) și 2 secvenţe maxdiv : 60 64 125 315 şi 315 24 150.

Exemplu 2:

maxdiv.in

7 2
22 60 64 125 315 24 150

maxdiv.out

60 64 125 315

Explicație

Cerinţa 2: Şirul de numere dat conţine 2 secvenţe maxdiv: 60 64 125 315 şi 315 24 150. Cea mai lungă secvenţă este 60 64 125 315.

#include <bits/stdc++.h>
using namespace std;
ifstream cin("maxdiv.in");
ofstream cout("maxdiv.out");
int n , cer , v[1002] , dmax , a[1002] , k , maxi , c1 , c2 , cnt;

int nrdiv(int n)
{
    int prod = 1 , d = 2;
    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()
{
    cin >> n >> cer;
    if(cer == 1)
    {
        for(int i = 1 ; i <= n ; i++)
        {
            cin >> v[i];
            a[i] = nrdiv(v[i]);
        }
        for(int i = 1 ; i <= n ; i++)
            if(a[i] > dmax) dmax = a[i];
        for(int i = 1 ; i <= n ; i++)
            if(a[i] == dmax) cnt++;
        cout << cnt - 1;
    }
    else
    {
        for(int i = 1 ; i <= n ; i++)
        {
            cin >> v[i];
            a[i] = nrdiv(v[i]);
        }
        for(int i = 1 ; i <= n ; i++)
            if(a[i] > dmax) dmax = a[i];
        for(int i = 1 ; i <= n ; i++)
            if(a[i] == dmax)
            {
                int j = i + 1;
                k = 1;
                while(j <= n && a[j] != dmax) j++ , k++;
                if(k > maxi && a[j] == dmax)
                {
                    maxi = k;
                    c1 = i;
                    c2 = j;
                }
                i = j - 1;
            }
        for(int i = c1 ; i <= c2 ; i++)
            cout << v[i] << ' ';
        }
    return 0;
}