[Java] [Spoj挑战]时间限制超过 - 如何让它更快？

Question

我的问题是我的代码在IDE上执行时效果很好但是它超过了Spoj的时间限制。我没有得到任何关于如何提高效率的暗示.Spoj challenge

这是我的代码：

import java.util.Scanner;

public class Factorial {

    public static int getDecomposition(int a) {
        int count = 0;
        int result = a;
        while (result % 5 == 0) {
            result /= 5;
            count++;
        }
        return count;
    }

    public static void main(String[] args) throws Exception {

        Scanner scan = new Scanner(System.in);
        int testCases = scan.nextInt();
        int sum[] = new int[testCases];
        int nums[] = new int[testCases];
        for (int i = 0; i < testCases; i++) {
            nums[i] = scan.nextInt();
        }
        for (int i = 0; i < testCases; i++) {
            for (int j = 5; j <= nums[i]; j = j + 5) {
                sum[i] += getDecomposition(j);
            }
            System.out.println(sum[i]);
        }
    }
}

Answer 1

我在想：以60为例（这是the linked challenges中的示例输入之一）。你在代码中的假设是正确的，对于每个从1到60的数字，你只需要考虑它可被5整除的次数，因为总有足够的数字被2整除，你将拥有这么多的零。那么从1到60的数字中有多少可以被5整除一次？答案：60/5 = 12.在这12个中，有多少可以再被5整除？ 12/5 = 2（忽略任何余数）。添加12和2（= 14）来记录，直到现在我们知道60的阶乘可被5 14倍整除。在这两个中，有多少可以在第三次被整除？ 2/5 = 0.一旦我们达到0，我们就完成了。答案是14（这与链接中的示例中的答案一致）。

因此，通过这种方式找到答案的算法。我认为它会比你发布的程序快一些。

也许你可以为我计算的总和找到一个不太复杂的公式，这样你就可以完全避免循环。也许你可以找到一些灵感here: Geometric progression。