0 
import java.util.*;  

class ModuloInverse {

    static long mod = 1000000007;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long num = in.nextLong();
        System.out.println(m_inverse(num, mod));
    }

    static long m_inverse(long a, long p) {
        return m_pow(a, p - 2);
    }

    static long m_pow(long n, long m) {
        long result = 0;

        if (m == 1) {
            return (n % mod);
        }

        if (m % 2 == 0) {
            result = m_pow(n, m / 2);

            return ((result * result) % mod);
        } else {
            result = m_pow(n, (m - 1) / 2);

            return (((n % mod) * (result * result)) % mod);
        }
    }
}

これは、乗法モジュロ逆数 (モジュロ 10^9+7) を計算するために私が書いた Java プログラムです。ただし、10 より大きい数値の出力として負の数値が返されます。何が問題なのかわかりません。

4

2 に答える 2

1

if一番下のステートメントにデバッグ行をいくつか追加しました。

    if (m % 2 == 0) {
        result = m_pow(n, m / 2);
        System.out.println("m = " + m + ", result = " + result + ", returning " + ((result * result) % mod));
        return ((result * result) % mod);
    } else {
        result = m_pow(n, (m - 1) / 2);
        System.out.println("m = " + m + ", n % mod = " + (n % mod) + ", result = " + result + ", returning " + (((n % mod) * (result * result)) % mod));
        return (((n % mod) * (result * result)) % mod);
    }

値 13 でこれを実行すると、これが出力された最後の行でした。

m = 1000000005、n % mod = 13、結果 = 846153852、-428497853 を返す

846153852 × 846153852 × 13 > 2 63なので、コードは Java の範囲を超えていますlong。

modは 10 9 + 7 であり、 が 0 と の間にある場合、result10 18をはるかに超えることはなく、1.1 × 10 18よりも確実に小さくなります。a が保持できる正の最大値は約 9.2 × 10 18であるため、約 9を超えると、この値を超える可能性があります。私が見る限り、これは最初に.modresult * resultlongnresult * result * nn = 13

2 つの数値のモジュロの積がmodJava の範囲を超えることはありませんがlong、3 つ以上の数値の積は超える可能性があります。

これを修正する1つの方法は、行を置き換えることです

return (((n % mod) * (result * result)) % mod);

と

return (((n % mod) * ((result * result) % mod) % mod);
于 2014-08-04T19:23:53.660 に答える
1 
But it gives negative numbers as output for numbers greater than 10

これは、すでにpositive overflowof に到達しているため、負のオーバーフローに戻る/開始するためです。

長い間、この値の範囲は、minimum value of -2^63 and a maximum value of 2^63-1そこに到達するまでの範囲であり、そこ2^63-1に戻って-2^63そこから開始します。

于 2014-08-04T18:28:22.550 に答える