蓝桥杯2023年第十四届省赛真题-阶乘的和
时间限制: 2s 内存限制: 320MB 提交: 3519 解决: 697
题目描述
给定 n 个数 Ai，问能满足 m! 为∑ni=1(Ai!) 的因数的最大的 m 是多少。其中 m! 表示 m 的阶乘，即 1 × 2 × 3 × · · · × m。
输入格式
输入的第一行包含一个整数 n 。
第二行包含 n 个整数，分别表示 Ai，相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
样例输入复制
3
2 2 2
样例输出复制
3
提示
对于 40% 的评测用例，n ≤ 5000 ；
对于所有评测用例，1 ≤ n ≤ 105 1 ≤ Ai ≤ 109 。
1.分析
1.计算n!的个数，如果个数恰好可以整除（n+1），它就可以变成（n+1）！的倍数。
2.重复第一步操作计算（n+1）！的个数，直到不能够整除为止，就是最大m。
3.可以用map存储，map会自动排序，遍历即可。
2.代码
#include<iostream>
#include<cmath>
#include<map>
#include<string>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAX = 1e6 + 10;
LL a[MAX], n;
map<LL, LL> m;
int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];m[a[i]]++; //计数}LL s = 0;for (auto it : m) {LL x = it.first, y = it.second;s = x; //记录最大的mif (y % (x + 1) == 0) { //判断是否可以整除（n+1）m[x + 1] += y / (x + 1);}else break; //不行就退出}cout << s << endl; //输出return 0;
}
