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 位整数扩展,就需要用多个较小整数实现相应运算。逐位取模的算法仍然适用。
备注:内容仅供参考。
