回覆列表
  • 1 # 使用者4783832246053

    模運算滿足的三個基本性質如下:(a + b) mod n = [ (a mod n + b mod n) ] mod n(a - b) mod n = [ (a mod n - b mod n) ] mod n(a * b) mod n = [ (a mod n) * (b mod n) ] mod n(a mod n) 就表示的是 (a 模 n),即程式中(a%n)的意思。比如 (13*15) mod 7 = [ (13 mod 7) * (15 mod 7) ] mod 7 = (6 * 1) mod 7 = 6上面這三條基本的性質的證明,可以參考 @鄧毅 先生的回答中

    a = c*k_a + z_a, b = c*k_b+z_b (z_a = a % c, z_b = b % c)的技巧,可以比較容易證明。記本問題中兩個很大的數分別為a、b,待求模的數字記為c。乍看之下即可用前面提到的第三條性質,分別計算a mod c、b mod c,然後計算其乘積,再對c求模即可。 但是,在@鍾宇騰先生回答中 @項昊凡先生的評論所提到的當a mod c、b mod c的結果都很大時,兩數相乘可能會產生資料溢位的情況,值得特別地考慮。一個直接的解決辦法是,將a mod c、b mod c的結果分別記為a1、b1,再利用同樣的思路對a1、b1做類似處理:(a * b) mod c = [ (a mod c) * (b mod c) ] mod c = [ (a1 * b1) mod c ] mod c = { [ (a1 mod c) * (b1 mod c) ] mod c } mod c若a1 mod c、b1 mod c仍然很大,其乘積仍然會溢位,則令a2=a1 mod c,b2=b1 mod c,再類似地處理即可。需要特別注意的是,在計算機處理中,不同語言對模運算的處理結果會不一樣。例如 -11 mod 7,按照一般數學上的定義,結果應該為 -4 mod 7 = 3,即結果總是為非負數;但在標準C中,總是有 x = (x / y) * y + x % y,則 -11 = -7 + (-11 % 7),從而結果為 -4,但是在Python shell中則結果是3。在模數和被模數符號相異時,需要特別注意這一點。此外,基於上面的三條基本性質,還有很多解法可供參考。考慮到 2*a*b = a*a + b*b - (a-b)*(a-b) = (a+b)*(a+b) - a*a - b*b注意到當a、b同號時,a-b不會溢位;當a、b異號時,a+b不會溢位。因此總可以有一種不會溢位的方式完成上面等式右邊的運算。可以發現,a*a,b*b,(a+b)*(a+b),(a-b)*(a-b),都是完全平方的形式。而一旦得到(2*a*b) mod c的結果也可以方便得出(a*b) mod c的結果。因此,結合上面的三條基本性質,原問題被轉為:一個很大的數的平方,模上另外一個數,如何在保證資料不會溢位的前提下得到結果?注意到,[ (c-a)*(c-a) ] mod c = [ (a -c)*(a-c) ] mod c = [ a*a + c*c - 2*a*c] mod c = (a*a) mod c類似地,有[ (c+a)*(c+a) ] mod c = [ a*a + c*c + 2*a*c] mod c = (a*a) mod c因此,比如當a>c,且同號的時候,利用(a*a) mod c 與[ (a-c)*(a-c) ] mod c相等,用a不斷地去減c,直到該結果的平方運算不會溢位為止。具體地,分為以下4種情況,(相等的平凡情況不影響,為表述方便忽略之):1)a > c,同號,已分析過;2)a > c,異號,此時a > 0,c < 0 採用 (a+c)*(a+c)運算,使a不斷地加上c,直至不會溢位;3)a < c,同號,類似採用(c-a)*(c-a)運算,直至不會溢位;4)a < c,異號,此時a < 0,c > 0,同情況 2)可以看到,類似地運用模運算的規律不難發現新的計算方法,上面談到的辦法也有許多可以最佳化的地方,比如在某些特殊情況下的簡便處理。此外模運算還有一個性質也是可以運用到該問題的求解中的:(a)(b) mod c = [ ((a) mod c)(b) ] mod c 其中(a)(b)表示數字地任意分割,12345=(12)345=(1)(2345)比如,125 mod 7 = (12mod 7)5 mod c = 55 mod 7這個結論也很容易證明,更多地相關性質可以參考 有限域 (finite field) 相關的內容。希望有所幫助,歡迎討論。

  • 中秋節和大豐收的關聯?
  • 寶寶多大可以吃紫菜半歲後食用最佳?