2

重複の可能性:
mod 1000000007 の質問でヘルプが必要

総積モジュロ 1000007 を計算したい一連の数値があります。たとえば、配列に 1000 個の数値が含まれている場合、次のように計算する必要があります。

int product = 1;
for(int i=0;i<Array_Max;i++)
  product = product * Array[i]

1000007 を法とする積 = ?

上記の疑似コードを最適化するアルゴリズムはありますか? 現在、オーバーフローのため商品を保管できません。

任意の提案をいただければ幸いです。

4

1 に答える 1

3

積には s を使用longします。これは、2 つの整数を乗算した結果を保持するのに十分です。

また、オーバーフローを回避するために、反復ごとにモジュロを計算する必要があります (これは、最後のモジュロ 1000007 の結果を変更しないため、数学的な観点から安全です)。

BigInteger必要に応じて sを使用することもできますが、はるかに遅くなります。

于 2012-06-10T16:42:13.540 に答える