求n!中因子k的个数

思路:

  求n的阶乘某个因子k的个数,如果n比较小,可以直接算出来,但是如果n很大,此时n!超出了数据的表示范围,这种直接求的方法肯定行不通。其实n!可以表示成统一的方式。

  n!=(km)*(m!)*a   其中k是该因子,m=n/k,a是不含因子k的数的乘积

下面推导这个公式

n!=n*(n-1)*(n-2)*......3*2*1

=(k*2k*3k.....*mk)*a  (a是不含因子k的数的乘积,显然m=n/k;n!中必定包含1到m个k相乘)

=(km)*(1*2*3...*m)*a    

=km*m!*a       (统计时ans+=m,然后继续去求m!中含有的k因子个数)

接下来按照相同的方法可以求出m!中含有因子k的个数。

因此就可以求除n!中因子k的个数

举例:

  比如要求8!中因子2的个数。

  原式=8!=1*2*3*4*5*6*7*8

   第一步:对8除2(21),相当于将1到8中所有“第一个”2因子提取出来。 (此时原式=1*1*3*2*5*3*7*4)

  第二步:对8除4(22),相当于将1到8中所有”第二个“2因子提取出来。 (此时原式=1*1*3*1*5*3*7*2)

  第三步:对8除8(23),相当于将1到8中所有”第三个“2因子提取出来。 (此时原式=1*1*3*1*5*3*7*1)

  第四步:对8除16(24),结果为0,退出循环。

实现:

 int count(int n,int k)
{
int num=;
while(n)
{
num+=n/k;
n/=k;
}
return num;
}
上一篇:求n!中含有某个因子个数的方法


下一篇:php 统计一维数组中重复的元素个数