2013-04-07 2 views
0

Я хотел бы вычислить:вывода ((а + Ь)/с) тойтом

((a+b)/c)mod m 

Я хотел бы знать, есть ли эффективный способ, так как a слишком большая, но b, c и m вписываются в простой 32-битный int.

+1

какой язык вы используете ... –

+1

.. и что вы подразумеваете под «слишком большим»? Больше, чем 32-битное число? Может ли он соответствовать 64-битным? – ysap

+1

Этот [ответ] (http://stackoverflow.com/a/3530661/180100) может помочь –

ответ

0

В модульной арифметике нет оператора деления. Вместо этого вы должны вычислить модульную инверсию знаменателя, а затем умножить. Таким образом, в вашем примере вы вычисляете a + b по модулю m, вычисляете модулярную инверсию c по модулю m, затем умножаем два по модулю m. Модульный обратный может быть найден с использованием расширенного евклидова алгоритма. Если вы не знаете, как вычислить модульный обратный, спросите.

+0

Как вы указали, вопрос не имеет смысла. –