整数の配列（サイズNの）とMの場合、配列のN-1要素の積をM剰余として求めます。M

Question

Aの整数はNで、もう1つの整数はMです。任意の所与の指数i0 <= i < Nため、Aのithインデックスを隠し、モジュロ例えばM.

の他のすべての要素の積を返し、次いでi=1ため、結果は(1x3x4x5) mod 100になりA = {1, 2, 3, 4, 5}とM=100を言います。したがって、結果は60です。

すべての整数は32ビットの符号なし整数であるとします。

これを行うための明らかなアプローチは、任意の与えられた値iの結果を計算することです。それはiの与えられたすべての値に対してN-1の乗算を意味します。これを行うより最適な方法はありますか？

P.S. 最初の考えは、すべての数字の積をAに保存することです（これはtotalとしましょう）。 iのすべての値に対して、totalをA[i]で除算し、モジュロを取った後の結果を返します。ただし、totalはオーバーフローの原因になるため、これは実行できません。

Answer 1

この回答は、これは1回限りの計算ではないと仮定していますが、これは何回も異なる値のiで何度も発生する可能性があります。

まず、計算された製品を保持する不揮発性アレイを定義します。 （上記の）アレイで

1. 空積を算出した場合、

2. 場合：次に

   、機能パラメータ（Mとi）の所定の対で呼び出されるたびにはい、単純に格納された値を使用し、MODを計算して結果を返します。

3. もしそうでなければ、製品を計算して保存し、MODを計算して値を返します。

この方法では、必要でない製品を計算する可能性がある（潜在的に長い）初期化を省くことができます。

Answer 2

簡単... ​​:)

left[0]=a[0]; 
for(int i=1;i<=n-1;i++) 
    left[i]=(left[i-1]*a[i])%M; 

right[n-1]=a[n-1]; 
for(int i=n-2;i>=0;i--) 
    right[i]=(right[i-1]*a[i])%M; 


for query q 
    if(q==0) 
     return right[1]%M; 
    if(q==n-1) 
     return left[n-2]%M; 
    return (left[q-1]*right[q+1])%M; 

5つの要素の配列があるとします。クエリqのためのクエリq = 3

answer is = ((1*5) * (10*4))%M 

のための今 今

index: 1 2 3 4 5 
     1 5 2 10 4 

= 4

answer is = ((1*5*2)*(4))%M 

私たちは、基本的にすべての左と右の乗算を計算する事前いる

index: 1  2  3 4 5 
     1  5  2 10 4 
left: 1  5  10 100 400 
right: 400 400 80 40 4 

---

For q=3 answer is left[2]*right[4]= (5*40)%M= 200%M 
For q=4 answer is left[3]*right[5]= (10*4)%M= 40%M