分割由多個陣列的整數的乘法以及採取

你有n個整數的數組模（整數可以像10^9一樣大）和你有q個查詢，每個查詢都有一個數組的索引，所以你必須乘以沒有那個特定索引的整數的數組，然後你有一個數字m，那麼，你必須用這個數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

我不想讓代碼告訴我應該是最優的方法。

來源

2017-10-17 Deepak Sharma

在實際的問題是米素？ – dmuir

您的問題的答案取決於m和列表中整數之間的關係。是素數？列表中的所有數字是否相對重要？如果其中任何一個如此，則有一個快速且簡單的算法。如果沒有，或者你不知道，最好的算法是較慢但仍然可行。 –

不，m不是素數 –

計算數組中所有整數的乘積。保存。

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

現在對於每個查詢，你的計算僅僅是

(product/query) %100;

來源

2017-10-17 15:30:14 user1717259

該產品可能變得非常大，非常快。簡單的整數數據類型將不夠用，BigIntegers會很慢。 –

我說整數可以大到10^9，所有這些整數的乘積都會導致溢出，所以這不是一個好的解決方案。 –

我能想到的一個解決方案，它包括遞歸使用模運算相對較小的數字。此解決方案可能需要很長時間才能計算，但它應該能夠輕鬆避免您遇到的溢出類型。

我們可以利用模運算的下列財產：

(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。

還有一點需要注意：對於此方法，如果有任何中間結果爲0，那麼最終結果也必須爲0。

編輯

如果您需要處理更小的數字，你可以使用模運算的下列財產（這是真的只是什麼已經如上圖所示的擴展名）：

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

通過這樣做，您不會處理大於a*b的數字，而只會處理大小爲(a mod c)*(b mod c)的數字，該數字必須小於或等於(c-1)^2（因爲x mod c必須小於或等於c-1）。當然，處理更小數字的權衡是，你的代碼會更復雜，執行時間稍長。

來源

2017-10-17 19:07:41 ImaginaryHuman072889

我也使用了相同的方法，但我在很多測試用例中得到了TLE –

我不確定是否有另一個選項。 – ImaginaryHuman072889

我可以想到的唯一可能加速計算時間（但增加內存使用量）的另一件事是爲您的程序利用一個數據庫（或者甚至僅僅是一個文本文件）來存儲模數運算解決方案的查找表。因此，不是每次都需要計算模數的程序，它只是在文本文件中查找值。 – ImaginaryHuman072889

分割由多個陣列的整數的乘法以及採取

回答

相關問題