0

私のコードのべき関数にいくつかの間違いがあり、小さな値に対しては正しい答えを返しますが、大きな値に対しては間違った答えを返します。

#include<stdio.h>
long long MOD= 1000000007;
long long power(long long i,long long j)
{
        if(j==0)
                return 1;
        long long d;
        d=power(i,j/(long long)2);
        if(j%2==0)
                return (d*d)%MOD;
        else
                return (d*d*i)%MOD;
}

int main()
{
        long long inv=1;
        inv=power(25,MOD-2)%MOD;
        printf("%lld\n",inv);
}
4

3 に答える 3

1

long long算術演算は、C実装のaで表現可能な値をオーバーフローしました。

また、「1000000007」を検索するとわかるように、StackOverflowで何度も議論されているチャレンジ問題や宿題に取り組んでいます。

于 2013-03-25T13:28:58.333 に答える
0

(d*d*i)%MOD;モジュロを使用しない複数の演算は、精度とオーバーフローのリスクを考慮して正しくないため、に注意する必要があります。厳密に正しくするには、次のように書く必要があります

 return ((d*d)%MOD * i)%MOD;

この場合でも私は仮定しましたi == i%MOD

編集：私は例を取ります：

log2((MOD-1)x(MOD-1)x25) = log2(1000000006x1000000006x25) = 64.438

これは、この入力を使用した計算中にオーバーフローすることを意味します。

于 2013-03-25T13:29:46.170 に答える
0

符号付きlonglongの範囲は-2^63〜（2 ^ 63 --1）で、最後のビットは符号を格納するために使用されます。あなたの場合、大きな数の乗算が評価されると、結果はオーバーフローし、数値の64番目のビット（符号を格納する）は値1（つまり-ve値）を取得します。

これが、出力として負の値を取得している理由です。

これを読む

于 2013-03-26T04:43:30.317 に答える