关于阶乘的两个问题

Love The Way You Lie 2022-08-06 12:29 217阅读 0赞

**关于阶乘的两个问题**

这篇介绍两个和阶乘运算相关的两个问题。切记，不可把阶乘的结果计算出来，因为会溢出。也不要转换为字符串来做，因为比较麻烦。一般而言，我们可以通过数学的方法，转化为结果和N有关，而不是N！的结果有关。

# 1. 计数N！末尾有几个零 #

给定一个N，计算N!的末端有几个零。这个问题如果把N！计算出来肯定是不现实的。像这种末尾计算有几个零，就是让你算N！的结果是10的多少倍，不是吗。。。类似的让你计算N！的结果的二进制形式最后又几个零，也即使让你计算N！是2的多少倍，这些问题都是相同的。

好了，既然我们知道要知道N！是10的多少倍，因为10不是质数，所以我们不可以直接把1~N都判断一遍，到底有多少数是10的倍数。这是因为假如一个数中有5，一个数有2的倍数，那么它们各自都不能被10除，而它们相乘就可以了~对吧~~所以以后要注意，这样的情况，一定要把10（或者其他的数）转换为质数。

好了，程序在下面，其中有些注意还是比较重要。一定要注意"有些数不只贡献1个，因为它可以被5除多次，所以要有这句".

其中为什么只计算5，而不是判断是否是2的倍数？这是因为自然数中2的倍数的自然数的个数要比5的倍数的自然数的个数多很多。既然要5和2同时出现，那么肯定是计算二者的较小者。比例2的倍数的数有10个，5的倍数的数有两个，那么满足10的倍数的要求一定是5个。

#include<iostream>
    using namespace std; 
    
    int count0(int N)
    {
    	int num = 0; 
    	for(int i = 1; i <= N; i++)  //因为是阶乘，所以要遍历1~N
    	{
    		int j = i; 
    		while(j % 5 == 0)  //能够被5除的数都算
    		{
    			num++; 
    			j /= 5;   // 有些数不只贡献1个，因为它可以被5除多次，所以要有这句
    		}
    	}
    	return num; 
    }
    
    int main()
    {
    	cout<<count0(100)<<endl; 
    	return 0; 
    }

如果要计算结果的二进制形式有几个零，可以直接用上面的程序，因为2是质数。

# **2. N！的二进制表示的最低位1的位置** #

题目的要求是确定N！的二进制表示中最低位1的位置，比如3！=6=0110，那么最低位的二进制就在低位的第二位。

当问题的规律咋看不出来的时候，我们可以先列几个数看看：

1 = 0001：在第1位；

2 = 0010：在第2位；

4 = 0100：在第3位；

8 = 1000：在第4位。

……

初步说明，N/2+1的个数就是答案，假如不能被2整除，那么就是1.

int lowestOne(int N)
    {
    	int num = 0; 
    	while(N)
    	{
    		N >>= 1; 
    		num += N; 
    	}
    	return num; 
    }