C++中大整数模运算问题：求((a*b*c)/n)%m的正确解法

你的错误在于模运算和除法不能随意交换顺序：先对乘积取模再除以n，得到的结果大概率不对——因为取模后的数值可能远小于n，整数除法会直接得到0，但实际的(a*b*c/n)的值可能远大于m，模m的结果自然不是0。

正确的思路是先把n的因子从a、b、c中约分掉，避免直接计算超大乘积溢出，再计算剩余数值的乘积模m。具体步骤如下：

步骤1：分步约分 #

利用最大公约数（GCD），依次将n的因子分摊到a、b、c上，直到n被完全约分为1（题目保证abc能被原n整除，所以最终n一定会变成1）：

• 计算a和当前n的GCD，将a除以这个GCD，同时n也除以这个GCD；
• 对b和当前n重复上述操作；
• 对c和当前n重复上述操作。

步骤2：安全计算乘积模m #

约分后的a、b、c数值已经足够小，不会直接溢出64位整数，但三个数相乘仍可能超过64位范围，所以需要用安全模乘法来计算：

• 如果编译器支持__int128（GCC、Clang等主流编译器都支持），可以直接用128位整数计算乘积再取模，简单高效；
• 如果不支持，实现一个基于二进制拆分的mul_mod函数，避免乘法溢出。

C++实现代码 #

#include <cassert>
#include <algorithm> // 用于swap

// 计算最大公约数（欧几里得算法）
long long gcd(long long x, long long y) {
    while (y != 0) {
        x %= y;
        std::swap(x, y);
    }
    return x;
}

// 安全模乘法：计算(x*y) % mod，用__int128实现（高效）
long long mul_mod(long long x, long long y, long long mod) {
    return (__int128)x * y % mod;
}

// 不支持__int128时，用二进制拆分实现mul_mod
/*
long long mul_mod(long long x, long long y, long long mod) {
    long long result = 0;
    x %= mod;
    while (y > 0) {
        if (y % 2 == 1) {
            result = (result + x) % mod;
        }
        x = (x * 2) % mod;
        y /= 2;
    }
    return result;
}
*/

// 核心计算函数
long long calculate(long long a, long long b, long long c, long long n, long long m) {
    // 分步约分n
    long long g = gcd(a, n);
    a /= g;
    n /= g;

    g = gcd(b, n);
    b /= g;
    n /= g;

    g = gcd(c, n);
    c /= g;
    n /= g;

    // 题目保证a*b*c能被原n整除，所以此时n必须为1
    assert(n == 1);

    // 计算(a*b*c) % m
    long long res = mul_mod(a, b, m);
    res = mul_mod(res, c, m);
    return res;
}

为什么这个方法可行？ #

通过约分，我们把(a*b*c)/n转化为了(a'/n1)*(b'/n2)*(c'/n3)，其中n1*n2*n3 = 原n，且a'=a/n1、b'=b/n2、c'=c/n3都是整数。这样既避免了直接计算超大乘积的溢出问题，又保证了最终计算的是正确的目标值，再对m取模就得到了正确结果。

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