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

の場合、aはサイズの算術を使用します。代わりに、オーバーフローしないより広い演算を使用してみてください。inta*ainta*(long long)a

于 2012-09-02T06:05:54.650 に答える