c++ - 计算大数的模数

Question

您好，我需要计算 (2^n + (-1)^n) % 10000007其中 1 < n < 10^9

我应该如何用 C++ 为它编写程序？

我知道这个模组属性(a + b)%n = (a%n + b%n)%n 但这对我没有帮助。

Answer 1

给定

(a + b)%m = (a%m + b%m)%m

然后，将 a 和 b 都替换为 2 的相同次方，得到递归:

2^k+1%m = (2^k%m + 2^k%m)%m

您可能已经想到您的公式可以让您将问题分解为:

(2ⁿ + (-1)ⁿ)%P = (2ⁿ%P + (-1)ⁿ%P)%P

然后，请注意 (-1)^k 要么是 1 要么是 -1，您应该能够在 O(n) 时间内计算出您的问题。