如何对指定数学公式取模并实现无特殊数据结构的C++代码

核心原理 #

因为模数M最大仅为1e9，且n不超过1e5，我们可以通过剥离M的所有质因子的方案，统一解决除法取模、阶乘取模为0的问题，全程仅需数组和基础循环即可实现，无需特殊数据结构。

具体实现步骤 #

1. 分解模数M的质因子 #

暴力遍历2到sqrt(M)，分解得到M的所有质因子及其对应幂次，存储为数组即可。例如M=12，分解得到{[2,2], [3,1]}，表示12=2²×3¹。

vector<pair<long long, int>> factor(long long M) {
    vector<pair<long long, int>> res;
    for (long long i = 2; i * i <= M; i++) {
        if (M % i == 0) {
            int cnt = 0;
            while (M % i == 0) {
                cnt++;
                M /= i;
            }
            res.emplace_back(i, cnt);
        }
    }
    if (M > 1) res.emplace_back(M, 1);
    return res;
}

2. 处理带除法的整数项（以((n-1)(n-2))/4为例） #

所有除法运算都通过约去公共质因子的方式转为乘法，避免分数问题：

1. 先提取分子每个因子中所有属于M的质因子，统计每个质因子的总幂次，剩余部分相乘后mod M。
2. 再提取分母每个因子中所有属于M的质因子，对应减去这些质因子的幂次，剩余部分求模M的逆元后乘到结果中。
3. 若任意质因子的剩余幂次小于0，说明该式在整数运算下无意义（若公式保证为整数则不会出现该情况）；若剩余幂次大于等于M中该质因子的幂次，则整个项mod M为0。

// 扩展欧几里得求逆元，适用于a和m互质的场景
long long exgcd_inv(long long a, long long m) {
    long long m0 = m, y = 0, x = 1;
    if (m == 1) return 0;
    while (a > 1) {
        long long q = a / m;
        long long t = m;
        m = a % m;
        a = t;
        t = y;
        y = x - q * y;
        x = t;
    }
    if (x < 0) x += m0;
    return x;
}

// 计算 ((n-1)*(n-2))/4 mod M，factors是M的质因子分解结果
long long calc_term(int n, long long M, vector<pair<long long, int>>& factors) {
    long long res = 1;
    vector<int> cnt(factors.size(), 0);
    // 处理分子 (n-1)*(n-2)
    auto process_num = [&](long long x) {
        for (int i = 0; i < factors.size(); i++) {
            long long p = factors[i].first;
            while (x % p == 0) {
                cnt[i]++;
                x /= p;
            }
        }
        res = res * x % M;
    };
    process_num(n-1);
    process_num(n-2);
    // 处理分母4=2^2
    long long den = 4;
    for (int i = 0; i < factors.size(); i++) {
        long long p = factors[i].first;
        while (den % p == 0) {
            cnt[i]--;
            den /= p;
        }
    }
    // 分母剩余部分和M互质，求逆元后相乘
    if (den > 1) {
        res = res * exgcd_inv(den, M) % M;
    }
    // 乘回剩余的质因子幂次
    for (int i = 0; i < factors.size(); i++) {
        if (cnt[i] >= factors[i].second) return 0;
        for (int j = 0; j < cnt[i]; j++) {
            res = res * factors[i].first % M;
        }
    }
    return res;
}

3. 处理阶乘模M（以(n-k)! mod M为例） #

同样用质因子剥离的方法，避免阶乘过大直接mod M为0导致后续计算错误：

// 计算 x! 剥离M的质因子后的剩余部分mod M，同时更新cnt数组存储各质因子的总幂次
long long fact_mod(int x, long long M, vector<pair<long long, int>>& factors, vector<int>& cnt) {
    long long res = 1;
    for (int i = 1; i <= x; i++) {
        long long tmp = i;
        for (int j = 0; j < factors.size(); j++) {
            long long p = factors[j].first;
            while (tmp % p == 0) {
                cnt[j]++;
                tmp /= p;
            }
        }
        res = res * tmp % M;
    }
    return res;
}

调用该函数后，若任意质因子的cnt值大于等于M中该质因子的幂次，则最终阶乘mod M的结果为0，否则将剩余质因子幂次乘入结果即可得到正确的阶乘模值。

性能说明 #

n最大为1e5，所有遍历操作的总时间复杂度为O(n log M)，完全满足性能要求。

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