Cerința

Se dau n numere naturale. Să se determine cel mai mare număr perfect mai mic sau egal cu 8128 care poate fi scris ca produs al unora dintre numerele date. Un număr natural este perfect dacă dublul său este egal cu suma divizorilor săi.

Date de intrare

Fișierul de intrare perfect1.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire perfect1.out va conține pe prima linie numărul S, reprezentând cel mai mare număr perfect care poate fi scris ca produs al unora dintre numerele de pe a doua linie a fișierului de intrare sau mesajul NU dacă nu se nu există un asemenea număr.

Restricții și precizări

• 1 ≤ n ≤ 100
• numerele de pe a doua linie a fișierului de intrare și numerele perfecte determinate vor fi mai mici decât 8128

Exemplul 1:

perfect1.in

7
2 7 9 2 2 31 2

perfect1.out

496

Explicație

înmultind 2*2*2*31*2 obținem numărul 496 .

Exemplul 2:

perfect1.in

6
2 31 127 2 2 5

perfect1.out

NU

#include <bits/stdc++.h>

using namespace std;

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

int n , A[101] , m , maxi , X[101] , x , ok;

void back(int k, long long p)
{
    for(int i = X[k - 1] + 1 ; i <= m ; i++)
    {
        X[k] = i;
        p *= A[X[k]];
        if(p <= 8128)
            if(p == 6 || p == 28 || p == 496 || p == 8128)
            {
                ok = 1;
                if(p > maxi) maxi = p;
            }
            else back(k + 1 , p);
        p /= A[X[k]];
    }
}

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> x;
        if(8128 % x == 0 || 496 % x == 0 || 28 % x == 0 || 6 % x == 0) A[++m] = x;
    }
    sort(A + 1 , A + m + 1);
    reverse(A + 1 , A + m + 1);
    back(1 , 1);
    if(ok == 0) cout << "NU";
    else  cout << maxi;
    return 0;
}