0
#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。你能说出问题出在哪里吗?

或者你能告诉另一种计算数字大幂的方法吗?

4

3 回答 3

1

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

于 2012-09-02T03:43:22.713 回答
0

<cmath>其中pow(x,y)x 是底数,y 是指数。x^y。

参考这里

于 2012-09-02T02:57:25.750 回答
0

什么时候aint,a*a使用- 大小的int算术。相反,尝试a*(long long)a使用不会溢出的更广泛的算术。

于 2012-09-02T06:05:54.650 回答