[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 个中，有多少个可以被三次整除？ 2 / 5 = 0。一旦我们达到 0，我们就完成了。答案是 14（这与 link 中示例中的答案一致）。

所以用这种寻找答案的方法做一个算法。我认为它会比您发布的程序快一些。

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

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

[Java][Spoj challenges] Time Limit Exceeds - How to make it faster?

java

time

limit