模运算减法恒等式问题及C++正确实现方案咨询

嘿，这个问题我之前做竞赛题的时候也踩过坑！模运算里的减法确实容易出问题，尤其是直接套用基础恒等式的时候，稍不注意就会得到负数或者溢出的结果，咱们一步步来解决它。

先搞清楚模减法的正确姿势 #

你提到的基础恒等式(a - b) % c = (a % c - b % c) % c本身数学上是对的，但在C++这类语言里，当被除数为负数时，取模结果会是负数，这就不符合我们想要的「非负余数」预期。

比如你给的例子：a=508, b=201, c=101，计算a%c=3，b%c=100，直接减得到3-100=-97，-97%101在C++里结果是-97，而实际正确的余数应该是4。

修正方法很简单：给差值额外加一个c再取模，确保中间结果是正数，最终恒等式变成：

(a - b) % c = (a % c - b % c + c) % c

用刚才的例子验证：(3-100+101)%101=4%101=4，完全符合预期。

针对大数阶乘模的C++实现方案 #

回到你的场景：计算大数阶乘模1e9+7，再减去更小的阶乘模，要解决负值和溢出问题，核心要注意两点：边算阶乘边取模、减法时用修正后的模运算公式。

1. 阶乘模的计算：避免溢出

直接计算大数阶乘肯定会溢出，所以必须每一步乘法后都取模1e9+7，这样每一步的结果都控制在0~1e9+6之间，用long long类型就能轻松存储（long long最大能存到9e18，完全hold住(1e9+7)*1e9的中间计算）。如果你的n特别大（比如超过1e9），可以用__int128处理中间乘法，避免溢出。

2. 减法处理：确保结果非负

当你得到两个阶乘模的结果fact_n和fact_k（n>k），直接相减可能出现fact_n < fact_k的情况（比如MOD=7，4!%7=3，3!%7=6，3<6），这时候用(fact_n - fact_k + MOD) % MOD就能保证结果是非负的。

完整代码示例 #

#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000007;

// 预计算阶乘模数组（适合多次查询的场景）
vector<long long> precompute_fact(int max_n) {
    vector<long long> fact(max_n + 1);
    fact[0] = 1; // 0! = 1
    for (int i = 1; i <= max_n; ++i) {
        // 用__int128处理超大数乘法，避免溢出
        fact[i] = ((__int128)fact[i-1] * i) % MOD;
    }
    return fact;
}

// 单次计算n的阶乘模
long long factorial_mod(int n) {
    long long res = 1;
    for (int i = 1; i <= n; ++i) {
        res = ((__int128)res * i) % MOD;
    }
    return res;
}

int main() {
    int n, k;
    cout << "请输入n和k（n > k）：";
    cin >> n >> k;

    // 方式1：预计算阶乘数组（如果需要多次查询）
    // vector<long long> fact = precompute_fact(n);
    // long long fact_n = fact[n];
    // long long fact_k = fact[k];

    // 方式2：单次计算
    long long fact_n = factorial_mod(n);
    long long fact_k = factorial_mod(k);

    // 核心：用修正后的模减法公式计算结果
    long long result = (fact_n - fact_k + MOD) % MOD;
    cout << "结果：" << result << endl;

    return 0;
}

关键注意点 #

• 数据类型：优先用long long存储模运算结果，超大数乘法用__int128过渡（C++大部分编译器都支持）。
• 预计算优化：如果需要多次查询不同阶乘的模，预计算一次阶乘数组比每次单独计算效率高得多。
• 模的一致性：所有运算都要统一用同一个模1e9+7，避免混乱。

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