题意：给定N个数a1,a2,a3...aN，现在要求最小的n满足 n!/(a1!*a2!*...*aN!) 是一个正整数的最小的n。
分析：这题的想法很明确，就是分解a1!*a2!*...*aN!，把其分解成质因子相乘的形式，这个都很熟悉了，然后就是对每一个质因子二分搜索出一个数字下界，最后求其中最大的一个数，问题的关键就是如何分解这样一个表达式成一个质因子相乘的形式。使用一个cnt数组来表示每一个数的在乘积中出现的次数，然后从后往前假设一个数出现了k次，那么如果这个数是素数则不用更新，如果一个数是合数则将其分解成两部分，一个是该数最小的质因子，一个是除以这个质因子之后的值，接着一直做下去，就能够把所有的素因子全部统计起来，最后再对每一个素因子都二分搜索。
#include#include #include #include #include #include #include using namespace std;typedef long long LL;const int N = 10000005;vector vv;LL cnt[N];int p[N];int Max;LL sum;int n;void pre() { for (int i = 2; i < N; ++i) { if (!p[i]) { p[i] = i; vv.push_back(i); } for (int j = 0; i*vv[j] < N; ++j) { p[i*vv[j]] = vv[j]; if (i % vv[j] == 0) break; } }}LL cal(LL mid, LL base) { LL ret = 0; while (mid) { ret += (mid /= base); } return ret;}void deal() { for (int i = Max; i >= 2; --i) { if (p[i] != i) { cnt[p[i]] += cnt[i]; cnt[i/p[i]] += cnt[i]; } }}LL get(LL base, LL x) { LL l = 1, r = sum; LL ret; while (l <= r) { LL mid = (l + r) >> 1; if (cal(mid, base) >= x) { ret = mid; r = mid - 1; } else { l = mid + 1; } } return ret;}int main() { pre(); scanf("%d", &n); int x; for (int i = 0; i < n; ++i) { scanf("%d", &x); sum += x; Max = max(Max, x); ++cnt[x]; } for (int i = Max-1; i >= 2; --i) { cnt[i] += cnt[i+1]; } // 模拟阶乘，1-n之间每个数都有一个 deal(); LL ret = 1; for (int i = 0; i < vv.size(); ++i) { ret = max(ret, get(vv[i], cnt[vv[i]])); } printf("%I64d\n", ret); return 0;}