java - 避免使用 BigInteger

Question

我有这个问题:

f(N) 是 N! 中尾随零之前的最后五位数字。

例如:11! = 39916800, f(11) = 99168

例如:13! = 6227020800, f(13) = 70208

找到 f(N)，其中 N 是您的函数输入。

我的解决方案是:

public static String Solving(int n) {

    if (n > 10) {
        String val;
        BigInteger z = BigInteger.ONE;
        for (int i = 1; i <= n; i++) {
            z = z.multiply(BigInteger.valueOf(i));
        }
        val = String.valueOf(z);
        val = val.substring(n % 10);
        val = val.substring(0, 5);
        return val;
    } else return "";
}

如何避免使用 BigInteger？

Answer 1

编辑:感谢 user58697 和 greybeard 的极好建议。

首先计算1->n中所有数中因子5的个数，

然后删除所有的 2 和 5 对，

最后计算结果模10^5。

static long mod = 100000;
public static long Solving(int n) {
    int five = 0;
    for (int power5 = 5, count ; 0 < (count = n / power5) ; power5 *= 5){ 
        five += count; 
    }

    // Number of pair (2,5) is the min number between 2 and 5
    int removeFactorTwo = five;
    int removeFactorFive = five;
    long result = 1;
    for(int i = 2; i <= n; i++){
        int st = i;
        while(st % 2 == 0 && removeFactorTwo > 0){
            st /= 2;
            removeFactorTwo--;
        }
        while(st % 5 == 0 && removeFactorFive > 0){
            st /= 5;
            removeFactorFive--;
        }
        result *= st;
        // This will make sure result always <= 10^5
        result %= mod;
    }
    return result;
}