Enunț

Având note mici la matematică, Gicuţa primeşte spre rezolvare următoarea problemă (uşoară pentru clasa a X-a) pentru a-şi mări nota: “Dându-se un şir X cu N numere naturale nenule: X 1 , X 2,…., X N, să se determine cel mai mare divizor prim dintre toti divizorii tuturor numerelor din şirul X“.

Enunț

Având note mici la matematică, Gicuţa primeşte spre rezolvare următoarea problemă (uşoară pentru clasa a X-a) pentru a-şi mări nota: “Dându-se un şir X cu N numere naturale nenule: X 1 , X 2,…., X N, să se determine cel mai mare divizor prim dintre toti divizorii tuturor numerelor din şirul X“.
Însă, pentru a obţine nota 10, el mai are de rezolvat o cerinţă a problemei: să determine cel mai mare număr care se poate forma din concatenarea divizorilor primi maximi ai fiecărui număr din şirul X.

Cerința

Scrieţi un program care să citească numărul natural N şi cele N numere naturale din şirul X şi care să determine:
1. numărul natural P reprezentând cel mai mare divizor prim dintre toţi divizorii tuturor numerelor din şirul X
2. cel mai mare număr natural K ce se poate forma din concatenarea divizorilor primi maximi ai fiecărui număr din şirul X.

Date de intrare

Fișierul de intrare divimax.in conține conţine N+1 linii. Pe prima linie sunt scrise doua numere naturale C și N, separate printr-un spațiu. Pe fiecare dintre următoarele N linii este scris câte un număr din şirului X, astfel încât pe linia i+1 din fişier este scris numărul Xi (1≤i≤N).

Date de ieșire

Fișierul de ieșire divimax.out va conține o linie.
– Dacă C=1, atunci se va rezolva doar cerința 1 a problemei, iar pe prima linie se va scrie numărul natural P reprezentând raspunsul la cerința 1.
– Dacă C=2, atunci se va rezolva doar cerința 2 a problemei, iar pe prima linie a fişierului se va scrie numărul natural K, reprezentând răspunsul la cerința 2.

Restricții și precizări

– 0 ≤ N ≤ 3030, N număr natural
– C=1 sau C=2
– 2 ≤ Xi ≤ 3500, unde 1 ≤ i ≤N
– Concatenarea a două numere inseamnă lipirea lor. (exemplu: Prin concatenarea numerelor 325 şi 684 rezultă numărul 325684, iar concatenându-le invers, obţinem 684325)
– Numărul determinat la cerinţa 2 poate avea cel mult 8000 de cifre
– Pentru rezolvarea corectă a cerinţei 1 se acordă 30% din punctaj, iar pentru rezolvarea corectă a cerinţei 2 se acordă 70% din punctaj.

Exemplul 1:

divimax.in

1 5
2 
36 
15 
12 
33

divimax.out

11

Explicație

C=1, se va rezolva doar cerinta 1.
Cel mai mare divizor prim al lui 2 este 2, cel mai mare divizor prim al lui 36 este 3, cel mai mare divizor prim al lui 15 este 5, cel mai mare divizor prim al lui 12 este 3, cel mai mare divizor al lui 33 este 11.

Exemplul 2:

divimax.in

2 7
23
44
10
204
4
45
9

divimax.out

5532321711

Explicație

C=2, se va rezolva doar cerinta 2.
Cei mai mari divizori primi ai numerelor sunt 23, 11, 5, 17, 2, 5, 3 (în ordinea în care sunt date în fişierul de intrare).

#include <bits/stdc++.h>

using namespace std;

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

int c, n, dmax=0, a[5001];
int f[4000];

void desc(int n){
    int d = 2;
    while(n > 1){
        int p = 0;
        while(n % d == 0)
            n/=d, p++;
        if(p && d > dmax)
            dmax = d;
        d++;
        if(d * d > n)
            d = n;
    }
}

int descmax(int n){
    int d = 2, maxi = 0;
    while(n > 1){
        int p = 0;
        while(n % d == 0)
            n/=d, p++;
        if(p && d > maxi)
            maxi = d;
        d++;
        if(d * d > n)
            d = n;
    }
    return maxi;
}

int putere(int n){
    int p = 1;
    while(n){
        p = p * 10;
        n/=10;
    }
    return p;
}

int concat(int a, int b){
    return a * putere(b) + b;
}

bool comp(int a, int b){
    return concat(a, b) > concat(b, a);
}

int main(){
    cin >> c >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    if(c == 1){
        for(int i = 1; i <= n; ++i)
            desc(a[i]);
        cout << dmax;
    }
    else{
        int b[10001];
        for(int i = 1; i <= n; ++i)
            b[i] = descmax(a[i]);
        sort(b + 1, b + n + 1, comp);
        for(int i = 1; i <= n; ++i)
            cout << b[i];
    }
    return 0;
}