2

我有一个数组 Array = {}，数组的大小是 n

我的约束是这样的：

n <= 100000 和数组i <=100

我必须找到数组中所有元素的乘积，我将得到一个 mod 值，我必须用它来修改乘积。mod 的值会一直变化，并且这个 mod 的值总是小于或等于 n。

我的问题是当我选择时，全局 mod 值说 R = 1000000000（远大于 mod 约束）并且每当我的产品超过这个值时，我都会修改结果。

但我不知道为什么我得到的结果是零。

我的问题是在这种情况下如何选择 R？

4

3 回答 3

1

我不知道你的代码，但很可能 0 是正确的结果。

选择 R 大素数并确保没有一个元素可以被这个数整除，以便得到不同于 0 的结果。

于 2013-08-10T12:14:19.400 回答
1

您还没有向我们展示您的代码，但大概它看起来类似于以下伪 Python 代码：

limit = 1000000

def product_mod( array, m ):
    product = 1 
    for k in array:
        product = product * k
        if product > limit: product = product % m

    return product % m

这个算法应该可以工作，只要限制足够低，product * k永远不会溢出。如果没有，您的代码中可能存在错误。

但是，请注意，这个函数的结果很可能经常合法地为零：具体来说，只要数组中数字的乘积除以模数，就会发生这种情况。由于乘积通常是一个高度复合的数字（它的因子至少与数组中的数字一样多），这很有可能。

特别是，只要：

  • 数组中的任何一个数字都为零，
  • 数组中的任何一个数字都是模数的倍数，或者
  • 数组中任何数字子集的乘积是模数的倍数。

在所有这些情况下，数组中所有数字的乘积将为零或模数的倍数（因此将减少为零）。

于 2013-08-10T12:12:11.247 回答
0

听起来您正在计算数组中的值对某个给定值取模的乘积，但正在使用另一个值来限制中间计算中的整数溢出。那么你就有很高的风险得到错误的结果。

例如 120 mod 9 = 3同时(120 mod 100) mod 9 = 20 mod 9 = 2

然后正确的程序是对所有计算模数与您用于最终结果的数字相同，因为(a * b) mod n = (a mod n) * (b mod n) mod n

例如 (24 * 5) mod 9 = (24 mod 9) * (5 mod 9) mod 9 = (6 * 5) mod 9 = 30 mod 9 = 3

于 2013-08-10T12:46:02.187 回答