模塊算術 - 分區

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 

這已經是容易計算的，因此我證明給這個作爲一個答案。我認爲你可以從那裏繼續你建議的更簡單的公式，但我沒有時間或傾向去解決這個問題。 （所以，如果這是家庭作業，那麼我留下一點讓你自己做:)）