#include <iostream> #include <cmath> long long k, N; bool tmp_p[99]; short p[99]; short *sequence; long long *partialValues; int from, to, changeIndex, len; bool stop; void decreaseVal() { while(sequence[changeIndex] == 0) { changeIndex--; } sequence[changeIndex]--; for(int i=changeIndex; i < len; ++i) { if (i == 0) { partialValues[i] = p[sequence[i]]; } else { partialValues[i] = partialValues[i - 1] * p[sequence[i]]; } } } void enlargeSequence() { if (len == to) { stop = true; } else { sequence[len] = sequence[len - 1]; partialValues[len] = partialValues[len - 1] * p[sequence[len]]; len++; } } int main() { std::cin >> k; std::cin >> N; for(int i=0; i<k; ++i) { short tmp; std::cin >> tmp; tmp_p[tmp - 2] = true; } int pCount = 0; for(int i=0; i<99; ++i) { if (tmp_p[i]) { p[pCount++] = i + 2; } } double logN = std::log(N); from = logN / std::log(p[pCount - 1]); to = logN / std::log(p[0]); sequence = new short[to]; partialValues = new long long[to]; for (int i=0; i<from; ++i) { sequence[i] = pCount -1; if (i == 0) { partialValues[i] = p[pCount - 1]; } else { partialValues[i] = partialValues[i -1] * p[pCount -1]; } } long long max = 0; len = from; stop = false; while(!stop) { changeIndex = len - 1; while(partialValues[len - 1] > N) { decreaseVal(); } if (partialValues[len - 1] == N) { std::cout<< partialValues[len - 1]; return 0; } if (max < partialValues[len - 1]) { max = partialValues[len - 1]; } enlargeSequence(); } std::cout << max; return 0; }
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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | #include <iostream> #include <cmath> long long k, N; bool tmp_p[99]; short p[99]; short *sequence; long long *partialValues; int from, to, changeIndex, len; bool stop; void decreaseVal() { while(sequence[changeIndex] == 0) { changeIndex--; } sequence[changeIndex]--; for(int i=changeIndex; i < len; ++i) { if (i == 0) { partialValues[i] = p[sequence[i]]; } else { partialValues[i] = partialValues[i - 1] * p[sequence[i]]; } } } void enlargeSequence() { if (len == to) { stop = true; } else { sequence[len] = sequence[len - 1]; partialValues[len] = partialValues[len - 1] * p[sequence[len]]; len++; } } int main() { std::cin >> k; std::cin >> N; for(int i=0; i<k; ++i) { short tmp; std::cin >> tmp; tmp_p[tmp - 2] = true; } int pCount = 0; for(int i=0; i<99; ++i) { if (tmp_p[i]) { p[pCount++] = i + 2; } } double logN = std::log(N); from = logN / std::log(p[pCount - 1]); to = logN / std::log(p[0]); sequence = new short[to]; partialValues = new long long[to]; for (int i=0; i<from; ++i) { sequence[i] = pCount -1; if (i == 0) { partialValues[i] = p[pCount - 1]; } else { partialValues[i] = partialValues[i -1] * p[pCount -1]; } } long long max = 0; len = from; stop = false; while(!stop) { changeIndex = len - 1; while(partialValues[len - 1] > N) { decreaseVal(); } if (partialValues[len - 1] == N) { std::cout<< partialValues[len - 1]; return 0; } if (max < partialValues[len - 1]) { max = partialValues[len - 1]; } enlargeSequence(); } std::cout << max; return 0; } |