|
求n的阶乘某个因子a的个数，如果n比较小，可以直接算出来，但是如果n很大，此时n!超出了数据的表示范围，这种直接求的方法肯定行不通。其实n!可以表示成统一的方式。 n!=(k^m)*(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; =(k^m)*(1*2*3...*m)*a =k^m*m!*a 接下来按照相同的方法可以求出m!中含有因子k的个数。 因此就可以求除n!中因子k的个数 int count(int n,int k)
{
int num=0;
while(n)
{
num+=n/k;
n/=k;
}
return num;
}
作者：Matrix海子
出处：http://www.cnblogs.com/dolphin0520/
本博客中未标明转载的**归作者Matrix海子和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在**页面明显位置给出原文连接，否则保留追究法律责任的权利。
| 
楼主
标题置顶
标题高亮
