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

Question

我的问题是我的代码在IDE上执行时运行良好，但它超过了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]);
}
}
}

Answer 1

我在想：以 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(这与链接中示例中的答案一致(。

因此，用这种方式来寻找答案。我认为它会比您发布的程序快一些。

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