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

Question

对于 CodeChef 问题 C_HOLIC2，我尝试遍历元素：5, 10, 15, 20, 25,... 并使用在 here 中指定的有效技术检查每个数字的尾随零的数量，但得到了TLE.

使用公式方法解决此问题的最快方法是什么？

Here is the Problem Link

Answer 1

我们知道计算一个数的阶乘中尾随零的数量，使用的技巧是：

5的倍数小于等于500的个数是500÷5=100

那么25的倍数是500÷25=20

那么125的倍数是500÷125=4

5的下一次幂是625，大于500

因此，尾随零的个数为100+20+4=124

查看详细解释this page

因此，这个计数可以表示为：

使用这个技巧，给定一个数字 N 你可以确定编号。其阶乘中的尾随零 count。 Codechef Problem Link

现在，假设我们得到了编号。尾随零，count，我们被问到最小的编号。 N 其阶乘具有 count 个尾随零 Codechef Problem Link

这里的问题是我们如何将count拆分成这个表示？

这是一个问题，因为在下面的示例中，正如我们所看到的，它变得困难了。

即使 no 以相同的数量增加，计数也会跳跃。正如您从下面的 table 中看到的那样，count 在其阶乘具有 5 的整数次幂的值处跳跃作为因子，例如25、50、...、125、...

+-------+-----+
| 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 =1×5+1)

在 N=31 之后，阶乘也将有一个因子 125。因此，对应于 25 的这些跳跃仍将以相同的频率发生，即在 31、37、43，...

现在125对应的下一次跳转会在31+31也就是62。因此125对应的跳转会发生在31,62,93,124.(区间=31=6 ×5+1)

现在625对应的跳跃会发生在31×5+1=155+1=156 因此你可以看到存在一个模式。我们需要找到此模式的公式才能继续。

形成的数列是1,6,31,156,... 这是 1 , 1+5 , 1+5+5² , 1+5+5²+5³ , ...

因此，第 n 项是 G.P 的 n 项之和。 a = 1, r = 5

因此，计数可以是 31+31+6+1+1 等。我们需要找到这个 t_n ，它小于 count 但最接近它。即

说这个数字是count=35，然后使用这个我们确定t_n=31 最接近。对于 count=63 我们再次看到使用这个公式，我们得到 t_n=31 是最接近但注意这里，31可以从count=63中减去两次。现在我们继续找到这个 n 并继续从 count 中减去 t_n 直到 count 变为 0.

使用的算法是：

        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ⁿ

我们举个例子来尝试解决这个问题：说计数 = 70，迭代 1：

迭代 2：

迭代 3：

再举个例子。假设 count=124，这是本页开头讨论的那个：迭代 1：

PS：所有图片完全归我所有。我不得不使用图像，因为 Whosebug 不允许嵌入 MathJax。 #WhosebugShouldAllowMathJax

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

CodeChef C_HOLIC2 Solution Find the smallest N whose factorial produces P Trailing Zeroes

series

factorial

zero

solution

trailing