題目描述

原題鏈接
階乘的和

問(wèn)題描述
給定 n 個(gè)數(shù) Ai?，問(wèn)能滿足 m! 為 ∑=(Ai!) 的因數(shù)的最大的 m 是多少。其中 m! 表示 m 的階乘，即 1×2×3×?×m。

輸入格式
輸入的第一行包含一個(gè)整數(shù) n。
第二行包含 n 個(gè)整數(shù)，分別表示 Ai?，相鄰整數(shù)之間使用一個(gè)空格分隔。

輸出格式
輸出一行包含一個(gè)整數(shù)表示答案。

樣例輸入

3
2 2 2

樣例輸出

3

題目分析

要點(diǎn)1：階乘之和的因數(shù)

n個(gè)不同的階乘Ai 之和的最大因數(shù)（可寫(xiě)成m！）即為n個(gè)階乘中的那個(gè)最小的階乘。

例如，
3個(gè)階乘：$2！4！3！$
之和為$2?1+4?3?2?1+3?2?1=32$，
能作其因數(shù)的階乘的最大值即為 $2！$

因?yàn)?#xff0c;要想做階乘之和的因數(shù)，則一定是各個(gè)階乘的因數(shù)，則最大因數(shù)一定為最小的那個(gè)階乘。

要點(diǎn)2：階乘之和的轉(zhuǎn)化

$i+1$ 個(gè) $i!$ 可轉(zhuǎn)化為 $(i+1)!$

例如，
$3$ 個(gè) $2!$ 為 $3?2!=3!$

因?yàn)?#xff0c;
$i+1$ 個(gè) $i!$為 $(i+1)?i!=(i+1)!$

整體分析

則我們可以記錄數(shù)據(jù)中最小的階乘 res ，
以及各個(gè)階乘出現(xiàn)的次數(shù)（便于進(jìn)行階乘的轉(zhuǎn)化）

scanf("%d",&n);unordered_map<int,int> map;  //map記錄Ai階乘的次數(shù)int res=2e9;  //res為階乘的最小值，設(shè)定初值為無(wú)窮大for(int i=0;i<n;i++){int a;  //階乘a!scanf("%d",&a);map[a]++;  //階乘a!出現(xiàn)次數(shù)+1res=min(res,a);  //找到Ai中的最小值res}

從階乘數(shù)最小的res開(kāi)始遍歷階乘，
若滿足 $map[i]\%(i+1)==0$，
則說(shuō)明存在 $i+1$ 個(gè) $i!$ ，可轉(zhuǎn)化為 $(i+1)!$，
且可轉(zhuǎn)為 $(i+1)!$的個(gè)數(shù)為$map[i]/(i+1)$.
否則，
更新階乘失敗，不存在更大的階乘因數(shù)，退出循環(huán)遍歷。

for(int i=res;;i++){if(map[i]%(i+1)==0){  //有i+1個(gè)i！，則可轉(zhuǎn)化為(i+1)!res=i+1;  //答案更新為i+1map[i+1]+=map[i]/(i+1);  //由i!轉(zhuǎn)化為map[i]/(i+1)個(gè)(i+1)!}else break;  //退出循環(huán)}

完整代碼

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
int n;
int main()
{scanf("%d",&n);unordered_map<int,int> map;  //map記錄Ai階乘的次數(shù)int res=2e9;  //res為結(jié)果，設(shè)定初值為無(wú)窮大for(int i=0;i<n;i++){int a;  //階乘a!scanf("%d",&a);map[a]++;  //階乘出現(xiàn)次數(shù)+1res=min(res,a);  //找到Ai中的最小值}for(int i=res;;i++){if(map[i]%(i+1)==0){  //有i+1個(gè)i！，則可轉(zhuǎn)化為(i+1)!res=i+1;  //答案更新為i+1map[i+1]+=map[i]/(i+1);  //由i!轉(zhuǎn)化為map[i]/(i+1)個(gè)(i+1)!}else break;}printf("%d",res);return 0;
}

?