牛客：阶乘结果换算进制后得到数字的尾部有几个0

时间：2018-11-17 21:49:34 阅读：200 评论：0 收藏：0 [点我收藏+]

题目

用十进制计算30！（30的阶乘），将结果转化成3进制进行表示的话，该进制下的结果末尾会有多少个0？

https://www.nowcoder.com/questionTerminal/14f881b32735445bb2af3494ce5f0e17?orderByHotValue=0&pos=29

链接：https://www.nowcoder.com/questionTerminal/14f881b32735445bb2af3494ce5f0e17?orderByHotValue=0&pos=29
来源：牛客网

对于3进制，3的质因数为3，将30！的每个因子分解成质因数的形式，末尾0的个数就是质因数的3的个数。我们只考虑3的倍数，3、6、12、15、21、24、30每个数贡献1个3，9、18贡献2个3，27贡献个3，因此质因数3的个数为1*7+2*2+3*1=14个

链接：https://www.nowcoder.com/questionTerminal/14f881b32735445bb2af3494ce5f0e17?orderByHotValue=0&pos=29
来源：牛客网

计算N！下三进制结果末尾有多少个0，其实就是计算三进制中的3被移位了多少次，就像二进制一样，每乘以2就向左移一位，末尾补0，因此这道题只要将N！因式分解成3^m*other，m就是答案。

技巧性的解法就是m=N/3+N/(3^2)+N/(3^3)....+N(3^k) (k<=N/3)，

用代码实现即为：

sum=0;

while(N){

sum+=N/3;

N=N/3;

}

return sum;

牛客：阶乘结果换算进制后得到数字的尾部有几个0

原文：https://www.cnblogs.com/captain-dl/p/9975716.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)