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

Question

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

atoi then "%" 和 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 是一个有效的以空字符结尾的字符串，表示一个没有任何空格/其他格式的大整数。