如何快速计数某一范围内(10^18)满足这种条件的数
大家好,这原本是一道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写成五进制后具有某种形式,怎么快速的找到某一范围内的具有这种形式的数的个数呢？ :L 全乱了，要是发帖前有个预览就好了 TeX 标签符前后界定的内容中若包含中括号时，往往会解析失效。
刚编辑了下主贴，不知是否为楼主要表达的意思？ 3# gxqcn
是的,谢谢
页:
[1]