1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
#include <vector>
#include <algorithm>

long long int maxDecomposable(const long long int max, const long long int limit, const std::vector<long long int>& primes, const unsigned int pStartIndex, const std::vector<long long int>& limitPrimesMaxFactor, const unsigned int pEndIndex)
{
    const long long int p = primes[pStartIndex];
    const long long int f = limitPrimesMaxFactor[pStartIndex];
    const unsigned int pNextIndex = pStartIndex + 1;
    long long int value = max;
    long long int newMax = max;

    while (true)
    {
        if (pStartIndex == pEndIndex)
            newMax = value;
        else
            newMax = std::max(newMax, maxDecomposable(value, limit, primes, pNextIndex, limitPrimesMaxFactor, pEndIndex));
        if (value <= f)
            value*= p;
        else
            break;
    }

    return newMax;
}

int main(int, char **)
{
    int k, p;
    long long int n;
    std::vector<long long int> primes;
    std::vector<long long int> limitPrimesMaxFactor;

    scanf("%d %lld", &k, &n);
    for (int i=0; i<k; ++i)
    {
        scanf("%d", &p);
        primes.emplace_back(p);
    }
    std::sort(primes.begin(), primes.end(), std::greater<int>());

    for (unsigned int i=0; i<primes.size(); ++i)
    {
        limitPrimesMaxFactor.emplace_back(n / primes[i]);
    }
    printf("%lld\n", maxDecomposable(1LL, n, primes, 0, limitPrimesMaxFactor, primes.size() - 1));
    return 0;
}