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