3

関数H（n）を計算したいここで

H(0)=0;
H(i)=H(i-1)×A+Ci mod B;

10<=A,B<=10^15;

Cはn個の要素の配列です

次のコードは時間がかかりすぎます...これを行うためのより良い方法はありますか？

public BigInteger H(int no) {              
    if(no>0) {
        bi=H(no-1);
        bi=bi.multiply(BigInteger.valueOf(A));
        bi=bi.add(BigInteger.valueOf(c[no-1]));
        bi=bi.remainder(BigInteger.valueOf(B));
        return bi;
    }

    return BigInteger.ZERO;

}

4

3 に答える 3

2

反復ごとに剰余を使用しないようにしてください。非常に遅い除算を使用します。

また、反復ごとに BigInteger.valueOf() を使用しないでください。A と B を BigInteger として 1 回だけ作成して保存します。それ以上行う必要はありません。

于 2010-08-08T17:00:34.460 に答える
-1

ええ、BigIntegersの世界へようこそ。

私が覚えていることの1つは、これに対して2つのパスを実行できることです。

1）BigIntegersを使用した低速パス2）両方の引数がMaxDouble未満の場合のdoubleプリミティブ型を使用した高速パス。

これで速度が少し上がるはずです。

ここでそれがどのように進んだかを教えてください、そして可能であれば時間を投稿してください。これは本当に面白いです。

于 2010-08-08T16:50:53.723 に答える