题目 3166: 蓝桥杯2023年第十四届省赛真题-阶乘的和--不能完全通过，最好情况通过67.

原题链接：

题目 3166: 蓝桥杯2023年第十四届省赛真题-阶乘的和
https://www.dotcpp.com/oj/problem3166.html

致歉

害，首先深感抱歉，这道题还是没有找到很好的解决办法。目前最好情况就是67分。

这道题先这样跳过吧，当然以后还是有看到能完全通过的，我能理解的题解，再进行补充。

下面对上述两种情况进行分析：
等等等等，首先还是的阐明解题思路，
贯彻一个核心点： m! 为∑ni=1(Ai!) 的因数的最大，即和的最大因数。

由于不太会使用这个编辑器里的公式，我就手写了哈，见谅

脑袋里要知道这个，这是解题的大前提，即我们要找到最小的可以mod数。

（1）时间超限62

这种结题思路，即求和，然后取阶乘，然后从1开始逐个数进行判断，

可以看到，最多会有$10^5$个数，数最大可以达到$10^9$，所以这种方法必然超时。

代码如下：

package 蓝桥__真题__专题;import java.io.*;
import java.util.Scanner;public class _2023试题F_阶乘的和02 {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int nextInt() throws Exception {st.nextToken();return (int) st.nval;}static long nextLong() throws Exception {st.nextToken();return (long) st.nval;}static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws Exception {int n = nextInt();int arr [] = new int[n+2];for (int i=1;i<=n;i++){arr[i] = nextInt();;}long ans =1L,p=1L;while (true){long sum = 0L;for (int i=1;i<=n;i++){long res=1;for (int j=2;j<=arr[i];j++){res=res*j%ans;}sum=(sum+res)%ans;}//--------------------------------------------if (sum==0){ans*=(++p);}else {break;}}//whilepw.println(p-1);//System.out.println(p-1);pw.flush();//scanner.close();}
}

解决思路：

1. 构造1-$10^9$的一个辅助数组之类的，存储这些数，这样求阶乘的时候，就可以直接得出来。
   但是这样遇到的问题有：

• 10^9这么大的数组，会爆
• 假如上一个是3！，下一个直接10！，中间的阶乘我都不知道，那我怎么快速定位到3！开始继续探索到10！

没想通，因此还是有很大的超时问题。

答案错误67

这是数学规律解法，但是还没完全找出所有规律，只发现了个浅显的，没空一直搞这个= =~
可以看到耗时非常短，

是上一种的20倍。

规律

大家有做，有思考几下的话，会发现一个普遍的规律，即：

大部分情况下满足：

• 只要总个数不等于最小的数min+1，那么所有输入的数中min就是我们要找的值。

从上面这个公式也可以看到，要在满足4！下继续去向下找，那么大概率肯定就是4！了。
当时肯定例外也是很多的了。

代码

package 蓝桥__真题__专题;import java.io.*;public class _2023试题F_阶乘的和06 {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int nextInt() throws Exception {st.nextToken();return (int) st.nval;}static long nextLong() throws Exception {st.nextToken();return (long) st.nval;}static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws Exception {int n = nextInt();int arr [] = new int[n+2];int min = Integer.MAX_VALUE;for (int i=1;i<=n;i++){arr[i] = nextInt();;if (arr[i]<min){min = arr[i] ;}}if (n==(min+1)){pw.println(n);}else {pw.println(min);}pw.flush();pw.close();}}