c++ - 计算一个数的大幂

Question

#include<iostream>
#include<cstdio>
#define M 1000000007
using namespace std;

long long int power(int a,int b)
{
    if(b==0)
        return 1;
    else if(b==1)
        return a;
    else if(b%2==0)
        return power((a*a)%M,b/2);
    else
        return (power((a*a)%M,b/2)*a)%M;
}

在这个函数中，当我传递 a=2, b>31 时，它总是返回 0。对于 b=31，我得到 147483634。你能告诉我问题出在哪里吗？

或者您能说出另一种计算一个数的大幂次的方法吗。

Answer 1

在 (a*a)%M 中，a*a 可能在计算余数之前溢出。从 2 开始，产生 0 的溢出并不让我感到惊讶。您需要使用能够表示 (M-1)*(M-1) 的类型，即 1000000012000000036，而 int 通常限于 2147483647。long long(标准从 99 年开始使用 C，从 11 年开始使用 C++，其他地方的通用扩展)保证有效。