现在的位置: 首页 > 综合 > 正文

不要被阶乘吓倒

2018年05月10日 ⁄ 综合 ⁄ 共 465字 ⁄ 字号 评论关闭

问题描述:给定一个整数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即可


【上篇】
【下篇】

抱歉!评论已关闭.