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

Question

对于 CodeChef 问题

C_HOLIC2

，我尝试迭代元素：

5, 10, 15, 20, 25,...

，并使用 here 指定的高效技术检查每个数字的尾随零的数量，但得到了 TLE。

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

这是问题链接

Answer 1

正如我们所知，计算数字阶乘中尾随零的数量，使用的技巧是：

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

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

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

5 的下一个幂是 625，大于 500。

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

详细说明请查看此页

因此，该计数可以表示为：

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

现在，假设我们得到了答案。尾随零，count，我们被问到最小的数字。 N，其阶乘有 count 尾随零 Codechef 问题链接

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

这是一个问题，因为在下面的示例中，我们可以看到它变得很困难。

即使 no 增加相同的数量，计数也会跳跃。 从下表中可以看出，计数跳跃的值的阶乘具有 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^th 项是 G.P. 的 n 项之和。其中 a = 1，r = 5

因此，计数可以是 31+31+6+1+1 等。 我们需要找到小于 count _{但最接近它的} tn。即

假设数字是 count=35，那么使用它我们可以确定 t_n=31 最接近。对于 count=63，我们再次看到，使用这个公式，我们得到最接近的 t_n=31，但请注意，这里，可以从 count=63 中减去 31 两次。现在我们继续找到这个n，并继续从count_中减去tn，直到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：所有图片完全归我所有。我必须使用图像，因为 StackOverflow 不允许嵌入 MathJax。 #StackOverflowShouldAllowMathJax