【数学推理】蓝桥杯第十四届---阶乘的和

题目描述

给定 n 个数 ，问能满足 m! 为 的因数的最大的 m 是多少。其中 m! 表示 m 的阶乘，即 1 × 2 × 3 × · · · × m。

输入格式

输入的第一行包含一个整数 n 。

第二行包含 n 个整数，分别表示 Ai，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

3
2 2 2

样例输出

3

提示

对于 40% 的评测用例，n ≤ 5000 ；
对于所有评测用例，1 ≤ n ≤ 10^5 1 ≤ Ai ≤ 10^9 。

---

（a!+b!+c!）(a<b<c) ，假设 b！是（a!+b!+c!）的最大因数那么一定是个小数（因为一定是一个小数，一定是整数），所以（a!+b!+c!）的最大因数一定是a!，如果有（a+1）个a!，那么 a!+a!+...+a!=(a+1)*a!=(a+1)! ，（如样例中的 2!+2!+2!=3*2!=3! ）。

---

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define int long long
const int N=1e5+10;
unordered_map<int,int> mp;
signed main(){
int n;
cin>>n;
int minv=1e9+10;
for(int i=1;i<=n;i++){
int x;cin>>x;
mp[x]++;
minv=min(minv,x);
}
while(mp.count(minv)){
int t=mp[minv]/(minv+1);
int k=mp[minv]%(minv+1);
if(k!=0) break;
mp[minv+1]+=t;
minv++;
}
cout<<minv<<endl;
return 0;
}

原文地址：https://blog.csdn.net/m0_74035601/article/details/137424415

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！