分割由多个阵列的整数的乘法以及采取

你有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

分割由多个阵列的整数的乘法以及采取

回答

相关问题