Критерии выбора мод значение

Question

У меня есть массив массива = {}, размер массива п

Мои ограничения, как это:

п < = 100000 и массив _я < = 100

Мне нужно найти продукты всех элементов в массиве, мне будет присвоено значение мод, с которым я должен модифицировать продукт. Мод будет изменять значения все время, и это значение мода всегда меньше или равно n.

Моя проблема в том, что я выбрал глобальное значение мод, скажем, R = 1000000000 (что намного больше, чем ограничение мод), и всякий раз, когда мой продукт превышает это значение, я изменяю результат.

Но я не знаю, почему результат Im получения равен нулю.

Мой вопрос: как я выбрал R в таких ситуациях?

Answer 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 может никогда не переполняется. Если это не так, у вас, вероятно, есть ошибка в коде.

Однако обратите внимание, что вполне вероятно, что результат этой функции может быть законно нулевым: в частности, это произойдет всякий раз, когда произведение чисел в вашем массиве равномерно делит модуль. Так как продукт обычно будет очень сложным числом (он будет иметь значение меньше столько факторов, сколько чисел в массиве), это довольно вероятно.

В частности, выход функции будет равно нулю, если:

• любое одно из чисел в массиве равно нулю,
• любое одно из чисел в массиве является кратным из модуль или
• произведение любого подмножества чисел в массиве кратно модулю.

Во всех этих случаях произведение всех чисел в массиве будет либо нулевым, либо кратным модулю (и, таким образом, будет уменьшено до нуля).

Answer 2

Я не знаю вашего кода, но похоже, что 0 правильный результат.

Пика R большое простое и убедитесь, что ни один из элементов не делится на это число, чтобы получить результат, отличный от 0.

Answer 3

Это звуки, которые вы вычисляя произведение значений в массиве по модулю некоторого заданного значение, но используют другое значение для ограничения переполнения целых чисел в промежуточных вычислениях. Тогда у вас есть высокий риск получить неправильный результат.

E.g.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