C++ : How to calculate modulo of a number raised to large power?

Question

我正在解决一个编程问题，我必须以 answer mod 10 ^ 9 + 7 的格式打印答案，其中“answer”是问题的实际答案。

我已经找到解决问题的算法，但需要注意的是，问题的答案始终采用 m * 10 ^ n 格式，其中

1 <= m <= 8 and 2 <= n <= 10^18，即答案中的10可以升到10^18的幂。当然直接计算10^n可能会溢出。

接下来我该做什么？

Answer 1

评估10^n mod M:

你需要的是Modular Exponentiation .它可以在 log_2(b)(log base 2)中计算 (a^b)%m。

示例

假设您需要计算 10^9。

1. 一种方法是依次多次 10、9 次。

2. 或者，使用分而治之的方法。

   10^9 = (10^8)*(10^1)

   10^8 = (10^4)*(10^4) :您需要计算 10^4 两次吗？

   10^4 = (10^2)*(10^2) :您需要计算 10^2 两次吗？

   10^2 = (10^1)*(10^1)

   10^1 = (10^1)*(10^0)

   10^0 是基本情况。

   所以，我们基本上做的是:

   1. 如果 power 是奇数，那么我们计算 base^(power-1) 并将其与 base 相乘得到 基础^力量。 [base^power = (base^(power-1)) * base)]
   2. 如果 power 是偶数，那么我们计算 base^(power/2) 并将它与自身相乘得到 base^power。 [base^power = (base^(power/2)) * (base^(power/2))]。但是我们只计算一次 base^(power/2)。

计算复杂度:

如前所述here :

A brief analysis shows that such an algorithm uses floor(log_2(n)) squarings and at most floor(log_2(n)) multiplications. More precisely, the number of multiplications is one less than the number of ones present in the binary expansion of n.

因此，我们可以说运行时间是 log_2(n) 的数量级。 (O(log_2(power)))

评估模数部分:

很容易注意到，在计算像 10^(10^18) 这样大的值时，我们必然会溢出甚至最大的原始类型(long long int)。在这里输入 Modular Multiplication , 根据 (a * b) % c = ((a % c) * (b % c)) % c。附带说明一下，当您直接查看代码时，您可能看不到正在使用此规则，但如果您评估递归调用，则会使用它。

问题解决了吗？

我们通过在运行时计算模数来防止溢出。比方说，如果我们得到一些值 10^9 并且我们需要将它与自身相乘。溢出？不，这次不是。

ans = ((10^9 % 1000000007) * (10^9 % 1000000007)) % 1000000007
ans = 10^18 % 1000000007
ans = 49

代码:

虽然有多种实现，但这里有一个简单的实现:

const int M = 1e9 + 7;
long long int powxy(long long int x, long long int y) {
    if (y == 0) return 1;
    if (y%2 == 1) return (x*powxy(x, y-1))%M;
    long long int t = powxy(x, y/2);
    return (t*t)%M;
}

已测试 here .