必需：存储在字符串模 11 中的大数字（最多 1000 位）

Question

我有个问题，就是求一个大数的模11。该数字存储在最大长度为 1000 的字符串中。我想用 C++ 对其进行编码。我该怎么办？

我试过用 long long int 来做，但它不可能处理极端情况的值。

Answer 1

用十进制表示的数a_na_{n-1}...a_0就是数

a_n*10^n+a_{n-1}*10^{n-1}+...+a_0

首先注意这个数字和数字

a_0-a_{1}+a_{2}+...+(-1)^{n}a_n

它的交替符号数字之和除以 11 后的余数相同。您可以通过减去两个数字并注意结果是 11 的倍数来检查。

基于此，如果给定一个由数字的十进制表示形式组成的字符串，那么您可以像这样计算余数模 11：

int remainder11(const std::string& s) {
  int result{0};
  bool even{true};
  for (int i = s.length() - 1; i > -1; --i) {
    result += (even ? 1 : -1) * ((int)(s[i] - '0'));
    even = !even;
  }
  return ((result % 11) + 11) % 11;
}

Answer 2

好的，这是魔术（数学）技巧。

首先假设您有一个仅由 1 组成的十进制数。

例如说111111。很明显111111 % 11就是0。（因为你总是可以把它写成一系列 11*10^n 的总和）。这可以推广到所有纯粹由偶数个 1 组成的整数。（例如 11、1111、11111111）。对于那些有奇数个的人，只需从中减去一个，你就会得到一个 10 乘以一些由奇数个 1 组成的数字（例如 111=1+11*10），所以它们对 [=16= 的模数] 将是 1.

十进制数总是可以写成

的形式

其中 a0 是最低有效数字，an 是最高有效数字。请注意，10^n 可以写成 10^n - 1 + 1，而 10^n - 1 是由 n 个九组成的数字。如果 n 是偶数，那么你会得到 9 乘以一些偶数，它对 11 的模总是 0。如果 n 是奇数，那么我们得到 9 乘以一些奇数，它对 11 的模总是 9。并且不要忘记我们在 10^n - 1 + 1 之后还有一个 +1，所以我们需要将 a 添加到结果中。

我们现在非常接近我们的结果：我们只需将所有内容相加并对 11 进行最终取模。伪代码如下：

Initialize sum to 0.
Initialize index to 0.
For every digit d from the least to most significant:
    If the index is even, sum += d
    Otherwise, sum += 10 * d
    ++index
    sum %= 11
Return sum % 11

必需：存储在字符串模 11 中的大数字（最多 1000 位）

Required: large number (max 1000 digits) stored in string modulo 11

c++

string

modulo

largenumber