algorithm - 模数 - 除法

Question

如何计算 (a/b) % m 其中 a = x1*x2*.. 并且数字 x1、x2、.. 非常大。

如果我们只需要找到一个 % m ，我们可以很容易地使用 (x1%m) * (x2%m) *...关于计算它？

我在某处读到此操作为 (a % (m*b)) / b 。我一直想知道这是不是真的，我们如何去证明它？

Answer 1

您至少可以做到这一点：

b * ((a / b) % m) = (b * (a / b)) % (b * m)
                  = (a - (a % b)) % (b * m)
                  = (a % (b * m) - (a % b) % (b * m))
                  = (a % (b * m) - (a % b))

hence,

((a / b) % m) = ((a % (b * m)) - (a % b)) / b

这已经更容易计算了，因此我有理由将其作为答案。我认为您可以从那里继续使用您建议的更简单的公式，但我没有时间或倾向于解决这个问题。（所以如果这是家庭作业，那么我会留一点给你自己做:)）