时间戳

首页 > 解决方案 > [Java][Spoj 挑战] Time Limit Exceeds - 如何让它更快？

java - [Java][Spoj 挑战] Time Limit Exceeds - 如何让它更快？

问题描述

我的问题是我的代码在 IDE 上执行时运行良好，但它超过了 Spoj 的时间限制。我没有得到任何关于如何提高效率的提示。Spoj 挑战

这是我的代码： 

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]);
        }
    }
}

标签： javatimelimit

解决方案

我在想：以 60 为例（这是链接挑战中的示例输入之一）。您在代码中的假设是正确的，即对于从 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（这与链接中示例中的答案一致）。

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

也可能你可以找到一个不太复杂的公式来计算我计算的总和，这样你就可以完全避免循环。也许你可以在这里找到一些灵感：几何级数。

推荐阅读