求n!中含有某个因子个数的方法

[复制链接]
552|0
 楼主| functions 发表于 2019-9-14 17:58 | 显示全部楼层 |阅读模式
求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的个数
  1. int count(int n,int k)
  2. {
  3.     int num=0;
  4.     while(n)
  5.     {
  6.         num+=n/k;
  7.         n/=k;
  8.     }
  9.     return num;
  10. }
练习题目:http://poj.org/problem?id=3219
作者:Matrix海子
    出处:http://www.cnblogs.com/dolphin0520/
    本博客中未标明转载的**归作者Matrix海子和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在**页面明显位置给出原文连接,否则保留追究法律责任的权利。


您需要登录后才可以回帖 登录 | 注册

本版积分规则

39

主题

446

帖子

1

粉丝
快速回复 在线客服 返回列表 返回顶部