学步园

问题描述

1、给定一个整数N，阶乘N！末尾有多少个0

2、求N！的二进制表示中最低位1的位置

1、给定一个整数N，阶乘N！末尾有多少个0

举例：10！＝3 628 800，则 N！的末尾有两个0

方法2尤巧。

公式：[N/k] = 1~N中能被k整除的数的个数

int FindZeroNum(int N)
{
	int nCount = 0;
	while(N)
	{
		N = N / 5;
		nCount += N;
	}
	return nCount;
}

第一次循环只处理5的倍数，例如：100，nCount = 0 + 100/5 = 20，贡献这20的数分别为1*5， 2*5， 3*5 ...20*5；

第二次循环只处理1~20中5的倍数，有4个，对应上一次循环中25的倍数。

以此往复。

2求N!的二进制表示中最低位1的位置

N！含有质因数2的个数 = N - N的二进制表示中1的个数