C++ 中两个大数的模

Question

我有一个名为 的类LargeNum，它通过数组存储大量数字，例如digit[]。因为int不够大，无法存放。

\n\n

基数为10000，因此数字的'9876 8764 7263'存储方式为\xef\xbc\x9a

\n\n

digit[4] = {9876, 8764, 7263};\n

\n\n

（底数可以改为10或100等digit[12] = {9,8,7,6,8,7,6,4,7,2,6,3}）

\n\n

问题是我想重载运算符%，这样 I\xe3\x80\x80 就可以得到两个大数的余数。大数之间的重载运算符*是-通过处理大数的每一位来完成的。但我真的不知道该怎么做%。喜欢：

\n\n

{1234,7890,1234} % {4567,0023}\n

\n\n

谁能帮我？

\n

Answer 1

伪代码应该是：

while digits_source > digits_base {
    while first_digit_source > first_digit_base {
        source -= base << (digits_source - digits_base)
    }

    second_digit_source += first_digit_source * LargeNum.base
    first_digit_source = 0
    digits_source--
}

while (source >= base) {
    source -= base
}

return source

这应该利用你的大数字的“数字”。

编辑：为了简单起见，我假设数组中的一个数字可以包含（从数字上讲）两个数字。如果不能，那么代码将变得非常棘手，因为你不能这样做second_digit_source += first_digit_source * LargeNum.base

编辑：

关于示例操作（基数 = 10000）

{65,0000,0099} % {32,0001}

照原样65> 32，然后继续执行：

65 - 32 = 33
0 - 1 = -1

然后我们就有了{33, -1, 99} % {32, 1}。再次继续

33 - 32 = 1
-1 - 1 = -2

我们有{1, -2, 99} % {32, 1}。因为 32 > 1，所以我们将源的前两位数字连接起来，得到{1*1000 - 2, 99} % {32, 1}。while现在我们可以通过简单的减法操作来进入简单的状态。while 进行了完整的比较，source >= base因为我们不能承受负数。然而，在算法的第一部分，我们可以，因为我们保证前两个数字的组合将为正。