我的幂函数有什么问题，它以 2 为底数，n 为指数并计算答案模 10^9+7？

Question

我的代码：

int power(int n)
{
    int num = 1000000007;
    if (n == 0)
        return 1;
    if (n%2 == 1)
    {
        int storage = power((n-1)/2);
        return (2*storage*storage)%num;
    }
    int storage = power(n/2);
    return (storage*storage)%num;
}

我已经使用 exponentiation by squaring 来提高效率，我知道有些地方不对劲，因为 n= 1000 的输出生成 495105785 而正确答案是 688423210 .

我什至尝试将 return 数据类型更改为 long long 以检查行 9 和 12 中可能发生的溢出，但答案仍然相同。任何帮助将不胜感激。

Answer 1

如果 int 为 32 位或更小，

storage * storage 可能溢出。使用溢出安全计算。

一个替代方案可以是 (int)(storage * 1LL * storage % num) 并且对于奇数幂情况类似。

Answer 2

storage * storage 有时可能会溢出 int 值，例如如果存储是 2^30 那么 storage * storage 是 2^60 它将被截断为 int 以适应 2^32 但你想要 full-size 计算否则你会得到错误的余数。使用 int64_t 作为中间结果，如下面的代码所示：

Try it online!

#include <cstdint>
#include <iostream>
using namespace std;

int power(int n)
{
    int64_t num = 1000000007;
    if (n == 0)
        return 1;
    if (n % 2 == 1)
    {
        int64_t storage = power((n - 1) / 2);
        return (2 * storage * storage) % num;
    }
    int64_t storage = power(n / 2);
    return (storage * storage) % num;
}

int main() {
    cout << power(1000) << endl;
    return 0;
}

输入：

输出：

688423210

我的幂函数有什么问题，它以 2 为底数，n 为指数并计算答案模 10^9+7？

What's wrong with my power function which takes 2 as base, n as exponent and computes answer modulo 10^9+7?

c++

exponentiation