分子分母公因数约简算法异常排查：组合数计算大测试失败

核心错误点 #

1. 未采用质因数分解的约简逻辑，无法处理复杂约简场景 #

你当前的实现直接存储阶乘的原数因子（比如3!存1、2、3），而非对每个数进行质因数分解。这种方式在小测试用例中能正常工作，但大测试用例中，当分母的因子无法被分子中的某个完整数整除时（比如分母有6，但分子中只剩3和2），代码找不到可整除的因子，会触发循环越界或错误结果。

组合数的本质是质因数的次数抵消，正确的思路应该是：

• 计算n!的质因数分解：对每个质数p，用公式floor(n/p) + floor(n/p²) + floor(n/p³) + ...计算它在n!中的出现次数
• 计算所有分母阶乘（a!、b!…x!）的质因数分解次数之和
• 将分子的每个质因数次数减去分母的对应次数（组合数为整数，结果次数不会为负），最后将所有质因数按次数相乘得到结果

2. 循环存在越界访问风险 #

你的while循环仅判断m->first % *l != 0就递增迭代器，没有检查m是否到达numeratorMultipliers.rend()。一旦当前分子中没有能直接整除分母因子的数（大测试用例中必然出现这种情况），循环会持续执行，直到访问超出map范围，导致程序崩溃或输出错误结果。

3. 约简后因子处理引入冗余复杂度 #

将m->first / *l直接加入分子的操作，可能引入合数（比如20/5=4），后续处理这些合数时，会增加约简的复杂度，更容易出现找不到可整除因子的情况，加剧越界风险。

修正方向 #

1. 替换存储结构，改用std::map<long long, int>存储质因数及其出现次数
2. 实现阶乘质因数分解函数：

   void factorizeFactorial(long long n, std::map<long long, int>& factors) {
       for (long long p = 2; p <= n; ++p) {
           long long temp = p;
           // 分解当前数的质因数
           for (long long i = 2; i * i <= temp; ++i) {
               while (temp % i == 0) {
                   factors[i]++;
                   temp /= i;
               }
           }
           if (temp > 1) {
               factors[temp]++;
           }
       }
   }
   

3. 分子调用该函数计算n!的质因数，分母对每个a!、b!…x!调用该函数并累加次数，再将分子次数减去分母次数
4. 最后将质因数按次数相乘，用大整数类型或字符串存储结果

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