计算递推序列s(n)的末尾零个数：现有代码n>30运行过慢求优化

你的问题核心在于直接计算超大数本身完全没必要——当n超过30时，s(n)的数值会爆炸式增长（毕竟是指数级的乘积递推），BigInteger的乘法和字符串转换都会变得异常缓慢，而且你其实只关心末尾的零个数，根本不需要完整计算这个数。

为什么末尾会有零？ #

末尾的零来自因数中的10，而10 = 2 × 5。每一对2和5的因子就会贡献一个末尾零。所以，我们只需要统计s(n)中2的因子总个数和5的因子总个数，取两者的最小值就是末尾零的数量。

递推公式转换 #

因为s(n) = s(n-1) × s(n-2)，所以对应的因子个数也满足递推关系：

• count2(n) = count2(n-1) + count2(n-2)
• count5(n) = count5(n-1) + count5(n-2)

其中count2(k)表示s(k)中2的因子个数，count5(k)同理。初始值就是s0和s1各自的2、5因子数。

优化后的代码实现 #

首先，我们需要一个辅助方法来计算单个数字中某个因子的个数：

private static int countFactor(int num, int factor) {
    int count = 0;
    while (num > 0 && num % factor == 0) {
        count++;
        num /= factor;
    }
    return count;
}

然后，用递推的方式计算到第n项的2和5的因子数，最后取最小值：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Soroco {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int s0 = Integer.parseInt(br.readLine());
        int s1 = Integer.parseInt(br.readLine());

        // 计算初始值的因子数
        int count2_0 = countFactor(s0, 2);
        int count5_0 = countFactor(s0, 5);
        int count2_1 = countFactor(s1, 2);
        int count5_1 = countFactor(s1, 5);

        if (n == 0) {
            System.out.println(Math.min(count2_0, count5_0));
            return;
        }
        if (n == 1) {
            System.out.println(Math.min(count2_1, count5_1));
            return;
        }

        // 递推计算到第n项
        int currentCount2 = 0;
        int currentCount5 = 0;
        for (int i = 2; i <= n; i++) {
            currentCount2 = count2_1 + count2_0;
            currentCount5 = count5_1 + count5_0;
            // 更新前两项的值，准备下一次迭代
            count2_0 = count2_1;
            count5_0 = count5_1;
            count2_1 = currentCount2;
            count5_1 = currentCount5;
        }

        System.out.println(Math.min(currentCount2, currentCount5));
    }

    private static int countFactor(int num, int factor) {
        int count = 0;
        while (num > 0 && num % factor == 0) {
            count++;
            num /= factor;
        }
        return count;
    }
}

顺便指出原代码的两个问题 #

1. 递归计算大数：递归本身就有额外开销，加上超大数的乘法，n=30之后必然卡顿，完全没必要。
2. 末尾零统计错误：你的countTrailingZeroes方法统计了字符串中所有的零，而不是仅末尾的零。比如1020会被统计为2个零，但实际末尾只有1个。正确的统计应该从字符串末尾往前数，直到遇到非零字符为止。

内容的提问来源于stack exchange，提问作者mavericktz