如何在C语言中计算超大数N对64位整数P的取模（N%P）

核心思路 #

利用模运算的分配律：(a * b + c) % p = [(a % p) * (b % p) + c % p] % p。由于超大数无法直接存储为常规数值类型，我们将其作为字符串处理，从左到右逐位迭代维护当前的模值：

• 初始模值设为0
• 每遍历一位数字，先将当前模值乘以10（模拟数字左移一位），再加上当前位的数字，最后对P取模，确保结果始终在P的范围内，避免溢出。

实现方案 #

方案1：利用__uint128_t简化计算（GCC兼容）

GCC支持128位无符号整数类型__uint128_t，可以直接容纳uint64_t *10的中间结果，无需额外处理溢出：

#include <stdio.h>
#include <string.h>
#include <stdint.h>

uint64_t big_mod(const char *n_str, uint64_t p) {
    if (p == 0) {
        fprintf(stderr, "Error: Division by zero\n");
        return 0;
    }
    uint64_t result = 0;
    const size_t len = strlen(n_str);
    for (size_t i = 0; i < len; ++i) {
        // 用__uint128_t存储中间值，避免uint64_t溢出
        result = ((__uint128_t)result * 10 + (n_str[i] - '0')) % p;
    }
    return result;
}

int main() {
    const char *n = "8290826691135830692772803";
    const uint64_t p = 95972011;
    printf("模运算结果：%llu\n", big_mod(n, p)); // 输出60316167
    return 0;
}

方案2：无128位整数支持时的兼容性实现

如果编译器不支持__uint128_t，可以用二进制分解乘法来避免溢出，通过循环加法模拟乘法并取模：

#include <stdio.h>
#include <string.h>
#include <stdint.h>

// 计算 (a * b) % mod，避免uint64_t溢出
static uint64_t multiply_mod(uint64_t a, uint64_t b, uint64_t mod) {
    uint64_t result = 0;
    a %= mod;
    while (b > 0) {
        if (b & 1) { // 若b为奇数，累加a到结果
            result = (result + a) % mod;
        }
        a = (a << 1) % mod; // a翻倍后取模
        b >>= 1; // b右移一位（除以2）
    }
    return result;
}

uint64_t big_mod(const char *n_str, uint64_t p) {
    if (p == 0) {
        fprintf(stderr, "Error: Division by zero\n");
        return 0;
    }
    uint64_t result = 0;
    const size_t len = strlen(n_str);
    for (size_t i = 0; i < len; ++i) {
        // 先计算当前结果*10 mod p，再加当前位数字后取模
        result = (multiply_mod(result, 10, p) + (n_str[i] - '0')) % p;
    }
    return result;
}

int main() {
    const char *n = "8290826691135830692772803";
    const uint64_t p = 95972011;
    printf("模运算结果：%llu\n", big_mod(n, p)); // 输出60316167
    return 0;
}

关键说明 #

• 两种方案均能处理长度达10000位的超大数字，时间复杂度为O(n)（n为数字字符串长度），效率足够。
• 必须处理P=0的异常情况，避免程序崩溃。
• 示例验证：输入题目中的N和P，两种方案均输出正确结果60316167。

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