找回密码
 欢迎注册
查看: 6656|回复: 4

[求助] 如何快速计数某一范围内(10^18)满足这种条件的数

[复制链接]
发表于 2012-10-15 19:03:01 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
大家好,这原本是一道projecteuler上的题,原本不适合公开讨论。但自己实在没看明白,忍不住想找个地方问问,就想到了这里,如果不方便,请版主删掉。
原题连接http://projecteuler.net/problem=383
原题如下:
$F(n)=x$ ,满足$5^x$ 整除 $n$,且$x$是最大的这样的数。如 $F(625000)=7$
$T(n) =y$ ,$y$是所有$1$到$n$之间满足$F[(2*i - 1)!] < 2*F(i !) $的$i$的个数。如$T(10^3)=68$,$T(10^9)=2408210$
问题是求$T(10^18)$
第一楼的算法很特别,但我断断续续看了很久还是不明白他是怎么计数的
因为
$F(n!) = \sum_{i=1}^{i=k}\frac{n}{5^i}   5^k <= n ;5^{k+1} > n$
将$2 * F(n!) $和$F[(2*i-1)!]$ 写成上面的形式
$\frac{2*n}{5^i} - \frac{2*i-1}{5^i} = {(1, 5^k | n) ,(0 ,other) ,(-1 , 5^k !| n & [(2*n-1)/5^k] " is odd"):}$
因此比较$2*F(i!)$与$F[(2*i-1)!]$可以比较对象项之差中$-1$和$+1$出现的次数

假设$2*n-1$写成五进制具有如下形式
$a_{n}a_{n-1}\cdots{a_l}44444 $ 则对应差中$1$会出现$l$次
$0$的出现对差没有影响
$-1$只需要 $k>l$ 且满足$a_{n}a_{n-1}\cdots{a_k}$为奇数即可

因此满足$2*F(i!) > F[(2*i-1)!]$
的$2*i-1$写成五进制后具有某种形式,怎么快速的找到某一范围内的具有这种形式的数的个数呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-10-15 19:05:02 | 显示全部楼层
全乱了,要是发帖前有个预览就好了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-10-16 09:20:55 | 显示全部楼层
TeX 标签符前后界定的内容中若包含中括号时,往往会解析失效。

刚编辑了下主贴,不知是否为楼主要表达的意思?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-10-16 09:36:44 | 显示全部楼层
3# gxqcn
是的,谢谢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 19:51 , Processed in 0.049851 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表