C++：如何计算一个数的大幂模数？

Question

我正在解决一个编程问题，我必须以答案 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。它可以计算 (a^b)%m in log_2(b)(log base 2).

例子

假设您需要计算 10^9.

一种方法是按顺序多次 10、9 次。
或者，使用分而治之的方法。

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 = (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。

C++：如何计算一个数的大幂模数？

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

c++

algorithm

number-theory

mod

正在评估 `10^n mod M`：

评估模数部分：

代码：

C++：如何计算一个数的大幂模数？

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

c++

algorithm

number-theory

mod

正在评估 10^n mod M：

评估模数部分：

代码：

正在评估 `10^n mod M`：