博客网 >

ZOJ1222,很汗~
作者:分类:默认分类标签:

求n!中的最低的非零数字位。比方说4!的最低非零位为4,5!的最低非零位为2。

最初的想法是,因为2*5=10,先找出2和5的数目来然后去掉即可。以前做过一个求n!末尾的多少零的题,因为因数5的数目远小于2,不停除5把结果加起来就是5的数目,也就是末尾零的数目。这题我想用同样的方法先求出5的个数,然后从1到n开始乘,中间遇到2就去掉,一直到去掉的2的个数与5的个数相同为止。这样做乘法时只需要保留个位数即可。

程序写好后输入100000都能瞬间出解,我心想没问题了,结果交上去是个TLE~~

没办法了去搜FORUM,说n最大能到10^100,巨汗……我这个自以为很厉害的算法瞬间崩溃……搜到了Lee.MarS大牛的解法,佩服之至,推荐一下:

http://acm.zju.edu.cn/forum/viewtopic.php?t=6952

其实我也想到了一点,但觉得不太可能,就没有深想那个特殊的除法,皑皑~~还有这种形式的递归在《具体数学》里多次出现的,但我还是没有想到,该注意了~~

<< 今天比较废~ / 一个小PHP完工~ >>

专题推荐

不平凡的水果世界

不平凡的水果世界

平凡的水果世界,平凡中的不平凡。 今朝看水果是水果 ,看水果还是水果 ,看水果已不是水果。这境界,谁人可比?在不平凡的水果世界里,仁者见仁,智者见智。

中国春节的那些习俗

中国春节的那些习俗

正月是农历新年的开始,人们往往将它看作是新的一年年运好坏的兆示期。所以,过年的时候“禁忌”特别多。当然,各个地方的风俗习惯不一样,过年的禁忌也是不一样的。

评论
0/200
表情 验证码:

RoBa

  • 文章总数0
  • 画报总数0
  • 画报点击数0
  • 文章点击数0
个人排行
        博文分类
        日期归档