C++计算含阶乘分数的公式模999999997时避免溢出的方法咨询

错误原因分析 #

• 之前计算错误的核心原因是直接使用浮点数（如247.5）参与模运算：浮点数存在精度截断问题，且模运算规则仅在整数域生效，无法直接对小数取模得到正确结果。
• 原式中的除法本质是整数整除，模运算场景下需要将除法转换为乘以模逆元的整数运算，才能保证所有步骤均为整数操作，结果符合预期。

公式化简 #

先对原式做通分化简，消去分式结构：
原式为：
$$(n - 1)! \times (\frac{n(n - 1)}{2} + \frac{(n - 1)(n - 2)}{4})$$
对括号内部分通分整理：
$$\frac{2n(n-1) + (n-1)(n-2)}{4} = \frac{(n-1)(3n - 2)}{4}$$
因此整体可化简为全整数运算的形式：
$$\frac{(n-1)! \times (n-1) \times (3n - 2)}{4}$$

分步取模计算规则 #

给定固定模数 MOD = 999999997（该值为质数，与4互质，因此4的模逆元存在），按以下步骤计算即可保证结果正确，且所有中间结果均不会超过64位整数范围：

1. 预处理阶乘模值：提前预计算1~100000的阶乘模MOD结果，避免重复计算：
   定义fact[0] = 1，递推公式为 fact[i] = (fact[i-1] * i) % MOD，fact[n-1]即为$(n-1)! \mod MOD$的结果。
2. 计算分子模值：所有乘法操作后立即取模，避免溢出：

   numerator = fact[n-1] * ((n - 1) % MOD) % MOD
   numerator = numerator * ((3 * n - 2) % MOD) % MOD
   

3. 预计算4的模逆元：根据费马小定理，质数模数下a的逆元为$a^{MOD-2} \mod MOD$，因此4的逆元为：
   inv4 = pow(4, MOD - 2, MOD) = 749999998
4. 计算最终结果：

   result = (numerator * inv4) % MOD
   

   若计算过程中出现负数，可再加上一次MOD保证结果为正整数。

场景验证（n=19） #

按上述步骤计算：

• fact[18] % MOD = 724935119
• 分子模值：724935119 * 18 % MOD * 55 % MOD = 685769961
• 最终结果：685769961 * 749999998 % MOD = 921442488，与直接计算的正确结果完全一致。

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