CodeChef C_HOLIC2解找到其阶乘产生P个尾随零的最小N

正如我们所知,在计算数字阶乘中尾随零的数量时,使用的技巧是:

小于或等于500的5的倍数为 500·5=100

然后,125的倍数是 500·125=4

因此,的尾随零的数量是

详细解释检查 this page

因此,该计数可以表示为:

使用此技巧,给定一个数字 您可以确定尾随零的数量 计数 在其阶乘中。 Codechef Problem Link

计数 N 其阶乘具有 计数 Codechef Problem Link

这里的问题是我们如何分裂

这是一个问题,因为在下面的例子中,正如我们所看到的,这变得很困难。

+-------+-----+
| count | N   |
+-------+-----+
| 1     | 5   |
+-------+-----+
| 2     | 10  |
+-------+-----+
| 3     | 15  |
+-------+-----+
| 4     | 20  |
+-------+-----+
| 6     | 25  |
+-------+-----+
| 7     | 30  |
+-------+-----+
| 8     | 35  |
+-------+-----+
| 9     | 40  |
+-------+-----+
| 10    | 45  |
+-------+-----+
| 12    | 50  |
+-------+-----+
| ...   | ... |
+-------+-----+
| 28    | 120 |
+-------+-----+
| 31    | 125 |
+-------+-----+
| 32    | 130 |
+-------+-----+
| ...   | ... |
+-------+-----+

你可以从这个任务的任何暴力程序中看到这一点,这些跳跃经常发生,即对于阶乘为25的数字,在6、12、18、24处 = 6=15+1

在N=31之后,阶乘的因子也将为125。因此,与25对应的这些跳跃仍将以相同的频率发生,即在31、37、43、。。。

现在,与125对应的下一个跳跃将在31+31处,即62处。因此,与125相对应的跳跃将发生在31、62、93、124处。(间隔 )

因此,你可以看到存在一种模式。我们需要找到这个模式的公式才能继续。

形成的序列是 1, 6, 31, 156, ... 这就是 1 , 1+5 , 1+5+5 ^2. +5 ^3.

因此,n 项是G.P.的n项之和,其中a=1,r=5

因此,计数可以是31+31+6+1+1等。 t _n 小于

说数字是 计数=35 _n =31 我们再次看到,使用这个公式,我们得到 t _n 最接近,但请注意,在这里,31可以从 计数=63 直到 计数

使用的算法是:

        count=read_no()

        N=0

        while count!=0:

            n=floor(log(4*count+1,5))

            baseSum=((5**n)-1)/4

            baseOffset=(5**n)*(count/baseSum)  // This is integer division

            count=count%baseSum

            N+=baseOffset

        print(N)

这里,5*n是5 ⁿ

迭代1:

迭代2:

迭代1:

附言 :所有的图片都完全属于我。我不得不使用图片,因为StackOverflow不允许嵌入MathJax#StackOverflowShouldAllowMathJax