除算私はあなたがn個の整数の配列を持っている <p></p>を、以下のようなもので、この質問に来た

Question

剰余を取ると、（整数は10^9と同じ大きさにすることができます）あなたはq個のクエリを持っています。すべてのクエリは配列のインデックスを1つ持っていますので、その特定のインデックスの整数を除いて配列を掛けなければなりません。そして、1つの数mを持ちます。 10^9まで）、各クエリの結果を返す。

e.g. suppose you have an array of n = 5 integers 
      1,2,3,4,5 
and you have q = 3 queries 1,3, 5 and mod value m = 100. 
for 1st query: (2*3*4*5) mod 100 = 20 
for 2nd query: (1*2*4*5) mod 100 = 40 
for 3rd query: (1*2*3*4) mod 100 = 24 
so output is 20,40,24 

私はコードがちょうど最適であるべきアプローチを教えたくありません。

Answer 1

配列内のすべてのintの積を計算します。それを保管してください。

int product = 1*2*3*4*5; 

は今クエリごとに、あなたの計算は単純

(product/query) %100; 

Answer 2

である私は、再帰的に比較的少数の剰余演算子を使用することを含む一つの解決策を考えることができます。このソリューションは、計算に時間がかかることがありますが、発生しているオーバーフローの種類を簡単に回避できる必要があります。

我々は、モジュラ算術の次のプロパティを利用することができます。

(a*b) mod c = ((a mod c)*b) mod c 

簡単な例は、以下を参照してください。これは、比較的小さな数値（経験するオーバーフローよりもはるかに小さい）を使用しますが、その点を実証しています。

---

(5*4*3*2*1) mod 7 

計算この「伝統的な方法」あなたがやるだけでしょう：

120 mod 7 = 1 

をしかし、我々は120

我々はできる限り大きく数字を使用することはできませんと言ってみましょうこれを行う：

(5) mod 7 = 5 (take this result as input to next line) 
      | 
      | 
+----------+ 
| 
| 
(5*4) mod 7 = 20 mod 7 = 6 
         | 
         | 
+-----------------------+ 
| 
| 
(6*3) mod 7 = 18 mod 7 = 4 
         | 
         | 
+-----------------------+ 
| 
| 
(4*2) mod 7 = 8 mod 7 = 1 
         | 
         | 
+----------------------+ 
| 
| 
(1*1) mod 7 = 1 mod 7 = 1 <--this is final result 

上記の結果（1）は、120 mod 7という計算を直接行うことと同じ結果になります。しかし、どの計算でも最大の数字は20でした。

もう1つ注意すべき点：この方法の場合、中間結果が0である場合、最終結果は0でなければなりません。

---

EDIT

あなたも小さい数字に対処する必要がある場合は、剰余演算の次のプロパティを使用することができます（実際には、既に上記示されているものの単なる延長である）：

a*b mod c = ((a mod c)*(b mod c)) mod c 

これを行うのではなく、a*bとして大きなとして数字を扱うことで、あなただけ以下でなければなりません、(a mod c)*(b mod c)として大きなとして数字を扱います（x mod cはc-1以下である必要があります）。もちろん、より小さい数値を扱う場合のトレードオフは、コードがより複雑になり、実行に少し時間がかかることです。