c++ - 在 C 中查找 100 位数字 mod 10^9+7 的值

Question

假设我得到了 100 位数字（输入可以是字符串）。我想找到那个数字 % mod 的值，其中 mod 是 10^9+7。我怎样才能得到答案。我已经使用字符串操作实现了大数的加法和减法函数。

提前致谢 ！

Answer 1

10 ⁹是 -7 模 1000000007。

从右侧开始，将 100 位数字N分成 9 位数字块（a ₀，a _{1 ，...）。}我们有：

N = a0 + a1*10^9 + a2*10^18 + ...

模数是₀ - 7*a ₁ + 49*a ₂ - ...

例如，假设您要计算 87564875326485487234854862386245865486238654862 模 1000000007。您将这个数字字符串从右边开始分成 9 块：

• 一个₀ = 238654862
• 1 ₌ 245865486
• 一个₂ = 245865486
• 一个₃ = 854862386
• 一个₄ = 485487234
• 一个₅ = 564875326
• 一个₆ = 87

现在将每个块转换为整数并计算 m = a ₀ - 7*a ₁ + 49*a ₂ - 323*a ₃ +...（提示：使用 64 位整数）。

现在N = m (mod 1000000007)。