UVAOJ 10061(未完结。续待)
发布日期:2022-03-30 20:19:26 浏览次数:33 分类:博客文章

本文共 395 字,大约阅读时间需要 1 分钟。

这题有点复杂,题目要求十进制数N!在B进制下表示后末尾的0个数和总的位数。

分析如下:

1.   求末尾0的个数:

思路是将N!分解为素数的积,记录下<=B的素数因子的个数(小于等于B的原因代码中解释了)。然后不断地从N!的因子中提取因子,使之刚好能乘积为B,则这几个因子可使N!在B进制下末尾产生一个0,直到提取不出为止。(当然,写代码的思路是不断分解B,当不能找到N!中小于等于B的因子用来分解B时结束)。记录下上述过程中B被分解了几次,即在末尾产生了几个0.

2.  求总的位数:

由于B进制下m位数所能表示的最大值在十进制下为B^m-1,故 

设总位数为m,则 B^(m-1) -1 < N! <= B^m -1,即 B^(m-1) <= N! < B^m

取10为底的对数得到:     (m-1)*log10(B) <= log10(N!) < m*log10(B)

故得到求总的位数m的方法。

转载地址:https://www.cnblogs.com/acmicpcstar/p/3690037.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:UVAOJ 350 基础题 伪随机数 数论
下一篇:C# Aes加密算法

发表评论

最新留言

关注你微信了!
[***.104.42.241]2024年03月23日 02时51分19秒