蓝桥杯：阶乘约数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 if(!st[i]) primes[++index] = i; for(int j = 1;primes[j]*i 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 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()); } } 文章来源
您阅读本篇文章共花了：
发表评论