首页 > 代码库 > 不要被阶乘吓倒
不要被阶乘吓倒
问题描述:给定一个整数N,那么N的阶乘N!末尾有多少个0呢?例如:N=10,N!=3628800,N!末尾有两个0
问题分析:算出N的阶乘再看他有多少个0肯定不实际,N稍微大点就极耗费时间空间,那么我们来分析一下什么时候会增加一个0呢,当存在2*5或者10的倍数时,其中10的倍数可以分解成(2*5)的n次方,很明显N!分解出来的质因子里面里面2的个数远远大于5,所以要知道N!有多少个0,只需要知道质因子里面5的个数即可。
简单代码:
优化:通过观察50!里面的数,5,10,15,20,25,30,35,40,45,50,我们可以发现每个5的倍数会贡献一个5,除此之外,每个25(5的平方)的倍数又另外贡献一个5。。。如此类推,5的n次方会在5的1次方、5的2次方.。5的n-1次方每次贡献一个5,到5的n次方再次贡献一个5,所以:
优化后代码:
拓展一:求N!二进制表示中最低位1的位置
问题分析:在10进制每乘以10后面就会多一个0,同理,在二进制中每乘以2就会多一个0,所以要知道最低位1的位置,只需知道N!的质因数中有多少个2即可
不要被阶乘吓倒
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。