蓝桥杯 阶乘的和（C++完整代码+详细分析）

题目描述

原题链接
阶乘的和

问题描述
给定 n 个数 Ai​，问能满足 m! 为 ∑=(Ai!) 的因数的最大的 m 是多少。其中 m! 表示 m 的阶乘，即 1×2×3×⋯×m。

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

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

样例输入

3
2 2 2

样例输出

3

题目分析

要点1：阶乘之和的因数

n个不同的阶乘Ai 之和的最大因数（可写成m！）即为n个阶乘中的那个最小的阶乘。

例如，
3个阶乘：$2！4！3！$
之和为$2\ast 1+4\ast 3\ast 2\ast 1+3\ast 2\ast 1=32$，
能作其因数的阶乘的最大值即为 $2！$

因为，要想做阶乘之和的因数，则一定是各个阶乘的因数，则最大因数一定为最小的那个阶乘。

要点2：阶乘之和的转化

$i+1$ 个 $i!$ 可转化为 $(i+1)!$

例如，
$3$ 个 $2!$ 为 $3\ast 2!=3!$

因为，
$i+1$ 个 $i!$为 $(i+1)\ast i!=(i+1)!$

整体分析

则我们可以记录数据中最小的阶乘 res ，
以及各个阶乘出现的次数（便于进行阶乘的转化）

scanf("%d",&n);
  unordered_map<int,int> map;  //map记录Ai阶乘的次数
  int res=2e9;  //res为阶乘的最小值，设定初值为无穷大

  for(int i=0;i<n;i++){
    int a;  //阶乘a!
    scanf("%d",&a);
    map[a]++;  //阶乘a!出现次数+1
    res=min(res,a);  //找到Ai中的最小值res
  }

从阶乘数最小的res开始遍历阶乘，
若满足 $map[i]\%(i+1)==0$，
则说明存在 $i+1$ 个 $i!$ ，可转化为 $(i+1)!$，
且可转为 $(i+1)!$的个数为$map[i]/(i+1)$.
否则，
更新阶乘失败，不存在更大的阶乘因数，退出循环遍历。

for(int i=res;;i++){
    if(map[i]%(i+1)==0){  //有i+1个i！，则可转化为(i+1)!
        res=i+1;  //答案更新为i+1
        map[i+1]+=map[i]/(i+1);  //由i!转化为map[i]/(i+1)个(i+1)!
    }
    else break;  //退出循环
  }

完整代码

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
int n;
int main()
{
  scanf("%d",&n);

  unordered_map<int,int> map;  //map记录Ai阶乘的次数
  int res=2e9;  //res为结果，设定初值为无穷大

  for(int i=0;i<n;i++){
    int a;  //阶乘a!
    scanf("%d",&a);
    map[a]++;  //阶乘出现次数+1
    res=min(res,a);  //找到Ai中的最小值
  }
  for(int i=res;;i++){
    if(map[i]%(i+1)==0){  //有i+1个i！，则可转化为(i+1)!
        res=i+1;  //答案更新为i+1
        map[i+1]+=map[i]/(i+1);  //由i!转化为map[i]/(i+1)个(i+1)!
    }
    else break;
  }
  printf("%d",res);
  return 0;
}

​