题目描述
给定 $n$ 个数 $A_i$,问能满足 $m!$ 为 $\sum\limits_{i=1}^n(A_i!)$ 的因数的最大的 $m$ 是多少。
其中 $m!$ 表示 $m$ 的阶乘,即 $1 × 2 × 3 × · · · × m$。
输入格式
第一行包含一个整数 $n$。
第二行包含 $n$ 个整数,分别表示 $A_i$,相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 $40\%$ 的评测用例,$n ≤ 5000$;
对于所有评测用例,$1 ≤ n ≤ 10^5,1 ≤ A_i ≤ 10^9$。
输入样例:
3
2 2 2
输出样例:
3
算法
C++ 代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100001;
int c[N];
int a[N];
int n;
signed main()
{
cin >> n;
int res = 2e9;
for(int i = 1;i <= n;i ++)
{
cin >> a[i];
if(a[i] < N) c[a[i]] ++;
if(a[i] < res) res = a[i];
}
for(int i = 1;i < N;i ++)
{
if(c[i] % (i + 1) == 0) // 如果这个阶乘的个数刚好可以往后分配
{
c[i + 1] += c[i] / (i + 1); // 就匀到后面去
}
else // 最大公因数就是 i 的阶乘
{
res = max(res, i); // 再取个 max
break;
}
}
cout << res << endl;
return 0;
}