使用BigInteger和备忘录模式高效判断阶乘首位数字奇偶性

List<Integer> process(int a, int b) {
    long base = i; // 这里的i应该初始化为1，并计算a!
    for(int i=1; i<=a; i++) base *= i; // 假设这里是计算a!

    if(even(base)) list.add(a); // 这里的even(base)在溢出后会给出错误结果

    for(int i=a+1; i<=b; i++) {
        base *= i; // 从a+1开始，base继续乘以i
        if(even(base)) list.add(i);
    }
    return list;
}

boolean even(long k) {
    // 将long转换为字符串，然后检查首位
    int z = ("" + k).charAt(0) - '0';
    return z % 2 == 0;
}

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class FactorialFirstDigitParity {

    // Fact 记录用于存储阶乘结果、对应的数字n以及首位数字的奇偶性
    // parity为true表示首位为偶数，false表示首位为奇数
    record Fact(BigInteger fact, int n, boolean parity) {}

    // 静态列表用于存储已计算的阶乘结果，实现备忘录模式
    // 初始化时包含0!, 1!, 2! 的结果
    static List<Fact> computed = new ArrayList<>(List.of(
            new Fact(BigInteger.ONE, 0, false), // 0! = 1 (首位为奇数)
            new Fact(BigInteger.ONE, 1, false), // 1! = 1 (首位为奇数)
            new Fact(BigInteger.TWO, 2, true)   // 2! = 2 (首位为偶数)
    ));

    /**
     * 判断给定数字 n 的阶乘首位是否为偶数。
     * 使用备忘录模式优化。
     * @param n 要计算阶乘的数字
     * @return 如果 n! 的首位为偶数，则返回 true；否则返回 false。
     */
    public static boolean factorialStartsWithEven(int n) {
        // 如果 n 小于等于当前已计算的最大阶乘数，直接从备忘录中获取结果
        if (n < computed.size()) {
            return computed.get(n).parity;
        }

        // 获取备忘录中最后一个已计算的阶乘结果
        Fact lastComputedFact = computed.get(computed.size() - 1);
        BigInteger currentFactValue = lastComputedFact.fact; // 从上一个阶乘值开始
        Fact result = null;

        // 从上一个已计算的数字 n+1 开始，逐步计算到目标 n
        for (int k = lastComputedFact.n + 1; k <= n; k++) {
            // 计算新的阶乘值： (k-1)! * k
            currentFactValue = currentFactValue.multiply(BigInteger.valueOf(k));

            // 获取当前阶乘值的字符串表示，并提取首位数字
            char firstChar = currentFactValue.toString().charAt(0);
            int firstDigit = Character.digit(firstChar, 10); // 将字符转换为数字

            // 判断首位数字的奇偶性
            boolean isEvenParity = (firstDigit % 2 == 0);

            // 创建新的 Fact 记录并添加到备忘录中
            result = new Fact(currentFactValue, k, isEvenParity);
            computed.add(result);
        }
        // 返回目标 n 的阶乘首位奇偶性
        return result.parity;
    }

    /**
     * 在指定范围内查找所有阶乘首位为偶数的数字。
     * @param start 范围的起始值
     * @param end 范围的结束值
     * @return 包含所有符合条件的数字的列表
     */
    public static List<Integer> getForRange(int start, int end) {
        List<Integer> results = new ArrayList<>();
        for (int i = start; i <= end; i++) {
            if (factorialStartsWithEven(i)) {
                results.add(i);
            }
        }
        return results;
    }

    public static void main(String[] args) {
        // 示例用法：查找 1 到 20 之间阶乘首位为偶数的数字
        List<Integer> list = getForRange(1, 20);
        System.out.println("在 [1, 20] 范围内，阶乘首位为偶数的数字有: " + list); 
        // 预期输出: [2, 3, 4, 8, 12, 13, 14, 16, 18, 20]

        // 示例用法：查找 1 到 10 之间阶乘首位为偶数的数字
        List<Integer> listSmallRange = getForRange(1, 10);
        System.out.println("在 [1, 10] 范围内，阶乘首位为偶数的数字有: " + listSmallRange);
        // 预期输出: [2, 3, 4, 8]
    }
}