algorithm - 找到 ((a +b)/c)mod m

Question

我想计算：

((a+b)/c)mod m

我想知道是否有任何有效的方法，因为ais too big but b，c 并且m适合简单的 32 位 int。

Answer 1

模算术中没有除法运算符。相反，您必须计算分母的模逆，然后相乘。因此，在您的示例中，您将计算 a+b 模 m，计算 c 模 m 的模逆，然后将两个模 m 相乘。可以使用扩展的欧几里得算法找到模逆。如果您不知道如何计算模逆，请询问。