c++ - C:将大数从字符串转换为以 n 为模的整数

Question

我正在尝试将非常大的数字(>100 位数字)从字符串转换为 Z_n 加法组(模 n)中的整数。 n 保证在标准 C int 范围内(例如 n=12345)。

无论是 atoi 然后“%”的简单方法，还是 BigIntiger 在这里都不起作用。

有什么想法可以实现吗？

Answer 1

我假设您的问题中指的是 C++(不存在 C/C++ 这样的东西)。 atoi 将字符串转换为适合标准整数(32 位)的数字，因此这不是您想要的。您必须编写自己的转换函数。

为了使数学简单，我们假设您的数字是正数。首先注意模数下的加法和乘法与没有模数时的加法和乘法是等价的。所以我们只需要保留这两个运算的结果，模n。然后注意我们可以逐位构造大数:

unsigned int convert(const char* s, int n) {
    long long x = 0;
    for (char *p = s; *p; p++) {
        x *= 10;
        x += (int)(*p - '0');
        x %= n;
    }
    return x;
}

为了清楚起见，我省略了任何错误检查。作为练习，编写一些附加代码以确保 s 是一个有效的空终止字符串，表示一个大整数，没有任何空格/附加格式。