蓝桥杯：阶乘约数

蓝桥杯：阶乘约数https://www.lanqiao.cn/problems/1020/learning/

目录

题目描述

        填空题：答案是 39001250856960000

题目分析

AC代码(Java)

暴力

线性筛

---

题目描述

        填空题

        定义阶乘 n!=1×2×3×⋅⋅⋅×n。

        请问 100! （100 的阶乘）有多少个正约数。

题目分析

        这道题考数论。

        这道题需要用到唯一分解定理：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积。

        

       上述式子中，N为大于1的自然数，P1为质数，为P1这个质数使用的次数。

        计算N的约数的话就是(1+)*(1+)*(1+)*....*(1+) 

        如180，可以唯一分解成: 2*2*3*3*5,写成定理的样子：*,那么他的约数个数就是(1+2)*(1+2)*(1+1) = 3*3*2 = 18个约数。

        在换成题目来说，我们求一下5！他有多少个约数。

        120 可以分解成 120 /2 = 60 ，60 /2 = 30 ， 30/2 = 15 ， 15/3 = 5 

        所以它可以表示成120=2*2*2*3*5，也就是**,所以它的约数为：(1+3)*(1+1)*(1+1) = 16个约数。

        但是我们要计算的是100！(100的阶乘)，不可能直接先把100！的具体值算出来在计算。

        所以我们根据5!来看，看看能不能拆分一下

        5!是 2*3*4*5， 那么，2可以表示成，3可以表示成，4可以表示成，5可以表示成。

        将他们组合一下，不就是变成了 

        合并一下，就是 

        然后根据定理找约数：(1+3)*(1+1)*(1+1) = 16。跟直接将120进行分解的结果一致。

        所以我们可以得到，5!只需要分别对2,3,4,5每个数进行唯一分解，得出使用的质数的数量(如2一共使用了3次，所以就是，最后继续合并，然后计算即可。

        知道了规律之后，就可以直接从1-100循环，每次将当前的i分解，将其分解出来的每个质数记录下来，令其使用次数+1。

        循环结束之后，就遍历我们记录质数使用次数的数组，然后根据质数的使用次数，如2这个质数使用了10次，那么就让 答案 乘上 （1+10）即可。

        因为我们将100！拆成了1-100之间每个数的质数组成，所以暴力也很快，绝对不会超过1s

        假设我们每次遍历，都需要将1-100之间的质数判断一下，那么撑死也就是100*100,也就是,1s出答案绰绰有余了。

        我分别写一个一个 普通遍历(暴力找质数) 和 线性筛模板 的方法。仅供参考。

AC代码(Java)

        需要注意的是，答案会很大，Java要用BigInteger，C的话开long long.

暴力

import java.math.BigInteger;// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {//唯一分解定理：任何一个正整数都可以分解成若干个质数的乘积//暴力求public static void main(String[] args) {//Java会爆long，要用大数BigInteger ans = new BigInteger("1");//记录每个质数出现的次数，只统计1-100的int[] target = new int[101];for(int i = 1;i<=100;i++) {int x = i;//把x拆成若干个质因数相乘，for (int j = 2; j <=x; j ++) {//如果j不为质数，就跳过if(!check(j)) continue;while(x % j == 0) {target[j] ++;x /= j;}}//如果循环结束了，那么需要查看x是否为1//为1则代表是任意一个质数的0次方，对应的值为(1+0),1乘进结果中结果不变，所以不用管//如果不为1代表还剩有质数没有处理,直接记录即可if(x > 1) target[x]++;}//统计完了1-100的所有质因数出现，我们就计算结果//根据唯一定理公式，每个质数的出现次数+1就是这个正整数中对应的计算 (1+array[j])for(int i = 2;i<=100;i++) {//i这个数没有出现过，不需要计算，直接跳过if(target[i] == 0) continue;//Java的大数运算很麻烦，需要创建相同的对象进行操作，还需要接受操作结果BigInteger x = new BigInteger(""+(1+target[i]));ans = ans.multiply(x);}System.out.println(ans.toString());}//判断是否为质数public static boolean check(int x) {for(int i = 2;i<=Math.sqrt(x);i++) {if(x % i == 0) return false;}return true;}
}

线性筛

        线性筛的话挺有趣的，有兴趣可以去了解一下，没兴趣的也可也背一下模板，比赛可能会用到。

import java.math.BigInteger;// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {//唯一分解定理：任何一个大于1的自然数N都可以分解成若干个质数的乘积//来一波线性筛把1-100的质数筛出来，直接暴力求也可以，我就当练习模板了static int N = 110;static int[] primes = new int[N];static boolean[] st = new boolean[N];public static void initPrimes(){int index = 0;for(int i = 2;i<N;i++) {if(!st[i]) primes[++index] = i;for(int j = 1;primes[j]*i<N;j++) {st[primes[j]*i] = true;if(primes[j] % i == 0) break;}}}public static void main(String[] args) {initPrimes();//Java会爆long，要用大数BigInteger ans = new BigInteger("1");//记录每个质数出现的次数，只统计1-100的int[] target = new int[101];for(int i = 1;i<=100;i++) {int x = i;//把x拆成若干个质因数相乘，for(int j = 1;j<x;j++) {while(x%primes[j] == 0){//primes[j]就是一个质数target[ primes[j] ]++;x /= primes[j];}}//如果循环结束了，那么需要查看x是否为1//为1则代表是任意一个质数的0次方，对应的值为(1+0),1乘进结果中结果不变，所以不用管//如果不为1代表还剩有因数没有处理if(x > 1) target[x]++;}//统计完了1-100的所有质因数出现，我们就计算结果//根据唯一定理公式，每个质数的出现次数+1就是这个正整数中对应的计算 (1+array[j])for(int i = 1;i<=100;i++) {//i这个数没有出现过，不需要计算，直接跳过if(target[i] == 0) continue;//Java的大数运算很麻烦，需要创建相同的对象进行操作，还需要接受操作结果BigInteger x = new BigInteger(""+(1+target[i]));ans = ans.multiply(x);}System.out.println(ans.toString());}
}