蓝桥杯笔记-2023年第十四届省赛真题-阶乘的和

给定 n 个数 Ai，问能满足 m!) 的因数的最大的 m 是多少。表示 m 的阶乘，即 1 × 2 × 3 × · · · × m。其中，2对应公式中的n，4!，所以4为输出答案。第二行包含 n 个整数，分别表示 Ai，相邻整数之间使用一个空格分隔。对于所有评测用例，1 ≤ n ≤ 105 1 ≤ Ai ≤ 109。n个Ai的阶乘之和得到的数，其最大因数 m!寻找几个数的阶乘之和的最大m!对于

文章共794字 · 阅读需要大约3分钟

一键AI生成摘要，助你高效阅读

问答

m0_64126000

3349人浏览 · 2023-11-11 19:45:26

m0_64126000 · 2023-11-11 19:45:26 发布

题目描述

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

输入格式

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

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

输出格式

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

样例输入

3
2 2 2

样例输出

提示

对于 40% 的评测用例，n ≤ 5000 ；
对于所有评测用例，1 ≤ n ≤ 105 1 ≤ Ai ≤ 109 。

问题重述

n个Ai的阶乘之和得到的数，其最大因数 m! 为是多少。

问题分析

寻找几个数的阶乘之和的最大m!，我们可以发现，m满足：

$a1!+a2!+...+an!=min(a1,a2,...,an)!*n$

例如2，2，2，3，3，3，4，其可以化为如下格式：

=>3*2!+3*3!+4!
=>3!+3*3!+4!
=>4*3!+4!
=>4!+4!
=>2*4!

其中，2对应公式中的n，4!为最大因数 m!，所以4为输出答案。然而4是怎么得到的呢？

我们可以以Ai最小值作为起点，如果min(Ai)的数量是Ai +1的整数倍，我们可以变为如下格式：

$a*Ai! = b*[(Ai)+1]!$

$[(Ai)+1]*b=a$

例如2 2 2 2 2 2 3可变为如下形式：

2* 2* 2* 2* 2* 2* 3
=>2*3*2!+3!
=>3*3!

根据如上规律，转换为代码。

参考代码

n = int(input())
dic = {}
l = list(map(int,input().split()))
minNumber = 1e10
#创建字典
for i in l:
    minNumber = min(i,minNumber)
    if i not in dic:
        dic[i] = 1
    else:
        dic[i] += 1

while dic[minNumber] >= minNumber + 1:
    #只有可以取余为0才可以是因数
    if dic[minNumber] % (minNumber + 1) == 0:
        #如果+1后的因数不在字典中，则创建
        if minNumber + 1 not in dic:dic[minNumber + 1] =0
        # 形如：2 2 2 3 3 3 4 4 4 4 
        # 因为3*(2!) = 3!
        #三个2的阶乘变为一个3的阶乘
        #=>3 3 3 3 4 4 4 4
        #因为4个3的阶乘可以变为4*(3!) = 4!
        #=> 4 4 4 4 4 => 5*(4!) = 5! => m = 5 ，5为最大因数
        dic[minNumber+1] += dic[minNumber] // (minNumber + 1)
        minNumber += 1
    else:
        break
print(minNumber)