为何输入20、75时出现Floating Point Exception？求代码排查帮助

让我们一步步拆解你遇到的问题，以及如何修复它：

1. 整数溢出导致的数值错乱 #

你的fact函数返回int类型，但阶乘的增长速度快得惊人：

• 32位int的最大值约为2^31-1 ≈ 2.1×10^9
• 而20! = 2432902008176640000，已经远超int的容量，溢出后会变成无意义的负数或乱码。

当A=20时，fact(A-1)=fact(19)的结果已经溢出，val1*val1的计算会进一步溢出，可能变成0或者负数，后续的val2/(...)就会触发除以零的错误（某些系统中整数除以零会报Floating Point Exception）。

2. 模运算的错误使用 #

你想要计算结果模1e9+7，但直接先做整数除法再取模是完全错误的：

• 模运算的除法不能直接用/运算符，因为模空间是有限域，除法需要用模逆元来替代，公式为：(a / b) mod MOD = a * inv(b) mod MOD，其中inv(b)是b在模MOD下的逆元。
• 你先计算val1*val1再取模，但此时val1已经溢出，这个结果本身就是错的，后续的除法自然也不对。

3. 最后一步除以A的错误 #

最后return (ans/A)%MOD同样犯了模运算除法的错误，直接用整数除法会丢失模运算的正确性，甚至因为溢出后的数值不是A的倍数，导致结果错误或异常。

修复后的代码 #

我们需要做几个关键调整：

• 用long long存储阶乘和中间结果，避免溢出，同时在计算阶乘的过程中就取模，防止数值过大。
• 使用快速幂计算模逆元，替代直接除法。
• 把递归的阶乘改成循环实现，避免递归深度过大导致栈溢出（比如A=75时递归深度74，虽然可能没问题，但循环更安全）。

const int MOD = 1000000007;

// 循环计算模MOD下的阶乘
long long fact(int num) {
    long long result = 1;
    for (int i = 1; i <= num; ++i) {
        result = (result * i) % MOD;
    }
    return result;
}

// 快速幂计算模逆元（MOD是质数，用费马小定理）
long long mod_inverse(long long base) {
    long long result = 1;
    long long exp = MOD - 2; // 费马小定理：inv(a) = a^(MOD-2) mod MOD
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }
    return result;
}

int Solution::solve(int A) {
    if (A == 0 || A == 1) {
        return 1;
    }
    long long fact_n_minus_1 = fact(A - 1);
    long long fact_2n_minus_1 = fact(2 * A - 1);
    
    // 计算分母：( (A-1)! )^2 * A mod MOD
    long long denominator = (fact_n_minus_1 * fact_n_minus_1) % MOD;
    denominator = (denominator * A) % MOD;
    
    // 计算结果：(2n-1)! * inv(denominator) mod MOD
    long long inv_denominator = mod_inverse(denominator);
    long long ans = (fact_2n_minus_1 * inv_denominator) % MOD;
    
    return static_cast<int>(ans);
}

为什么这样修复？ #

1. 阶乘计算过程取模：确保每一步的结果都在long long的范围内，避免溢出，同时保证模运算的正确性。
2. 模逆元替代除法：利用费马小定理（因为1e9+7是质数），计算除数的逆元，把除法转化为乘法，符合模运算的规则。
3. 循环实现阶乘：避免递归深度过大导致的栈溢出问题，同时效率更高。

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