PAYATHON 2026

C 中如何计算超大整数 N 对 64 位整数 P 的取模结果?

技术老齐

把 N 作为十进制字符串,从左到右逐位计算余数即可。计算时只需保存当前余数,不需要 BigInteger 或 GMP。

即使余数能用 64 位整数保存,更新余数时的 r * 10 + digit 仍可能溢出。要支持完整的 64 位模数范围,就必须避免这个中间结果溢出。

逐位取模的原理

假设已读入的数字组成整数 A,下一位数字是 d,读入这一位后,新整数为:

[ 10A+d ]

根据取模运算的性质:

[ (10A+d)\bmod P

(10(A\bmod P)+d)\bmod P ]

从 r = 0 开始,每读入一位数字,就按下面的公式更新余数:

r = (r * 10 + digit) % p;

读完所有数字后,r 就是 N % P。

这里约定 N >= 0、P > 0,输入字符串只包含十进制数字。

为什么不能直接乘以 10

每一步都满足:

[ 0 \le r < P ]

但 10 * r + digit 最大可达 10 * P - 1。当 P 接近 64 位整数上限时,这个中间结果可能超出类型范围。

无符号整数溢出有规定的回绕行为,但回绕后再 % P,通常得不到原来的数学余数。有符号整数溢出则属于未定义行为。

如果能保证中间结果不超过所用类型的最大值,可以直接使用上述公式。否则,需要通过不会溢出的模加法完成 10 * r + digit 的取模计算。

不依赖更宽整数类型的代码

先实现 (a + b) % p,前提是 a < p、b < p:

  • 如果 a >= p - b,结果为 a - (p - b)。
  • 否则,a + b < p,可以安全相加。

再通过倍增依次计算 2r、4r、8r 对 p 的余数,最后将 8r 和 2r 的余数相加并取模,得到 10r % p。

下面的代码使用 unsigned long long,要求运行环境支持该类型和 printf 的 %llu 格式。两者都属于 C99,部分更早的 GCC 环境也通过扩展提供支持,是否可用要以评测环境为准。

#include <stdio.h>

typedef unsigned long long uint64_type;

/* Requires: p > 0, a < p, b < p. */
static uint64_type add_mod(uint64_type a,
                          uint64_type b,
                          uint64_type p)
{
    if (a >= p - b)
        return a - (p - b);

    return a + b;
}

/* Returns 1 on success, 0 for invalid input. */
static int decimal_mod(const char *s,
                       uint64_type p,
                       uint64_type *result)
{
    uint64_type r = 0;
    uint64_type r2, r4, r8, digit;

    if (s == NULL || result == NULL || p == 0)
        return 0;

    if (*s == '\0')
        return 0;

    while (*s != '\0') {
        if (*s < '0' || *s > '9')
            return 0;

        digit = (uint64_type)(*s - '0');

        r2 = add_mod(r, r, p);
        r4 = add_mod(r2, r2, p);
        r8 = add_mod(r4, r4, p);

        r = add_mod(r8, r2, p);
        r = add_mod(r, digit % p, p);

        ++s;
    }

    *result = r;
    return 1;
}

int main(void)
{
    const char *n = "8290826691135830692772803";
    uint64_type p = 95972011ULL;
    uint64_type remainder;

    if (!decimal_mod(n, p, &remainder)) {
        fputs("Invalid input\n", stderr);
        return 1;
    }

    printf("%llu\n", remainder);
    return 0;
}

输出为:

60316167

digit % p 不能省略,因为 add_mod 要求两个加数都小于 p。当 p 小于或等于当前数字时,直接传入 digit 就不满足这个条件。

输入规模和旧编译器的注意事项

设 N 有 k 位,每位只执行固定次数的模加法,时间复杂度为 O(k);除输入字符串外,额外空间为 O(1)。也可以用 getchar() 逐个读取数字,边读边更新余数,省去存储整个字符串的空间。

如果允许 N 等于 (10^{10000}),十进制表示最多有 10001 位。使用字符数组时,还要为字符串结束符 '\0' 留一个位置,因此至少需要 10002 个字符。读取输入时也应限制长度。

另外:

  • P = 0 时取模没有定义,代码会拒绝这种输入。
  • 前导零不影响结果;P = 1 时结果总是 0。
  • 示例不接受正负号或空白字符。如果允许负数,需要单独处理符号,并明确采用 C 的余数规则还是非负数学模。
  • 在支持 unsigned long long 的标准 C 实现中,该类型至少有 64 位,足以保存任意无符号 64 位模数。不能假定 long 一定是 64 位。
  • 如果环境严格只支持 C90,也没有可用的 64 位整数扩展,就需要用多个较小整数实现相应运算。逐位取模的算法仍然适用。

备注:内容仅供参考。