模块算术 - 分区

Question

如何计算（a/b）％m其中a = x1 * x2 * ....以及数字x1，x2，..都相当大。

如果我们只需要找到％m，我们可以很容易地用（x1％m）*（x2％m）* ...做到这一点......但是如果在我们的例子中分母'b'中有某些东西，如何计算它呢？

我在某处读了这个（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 

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