[Visual Basic 6.0] 計算 A^B Mod C ( A 的 B 次方除以 C 的餘數 )

2013-11-04

摘要:[Visual Basic 6.0] 計算 A^B Mod C ( A 的 B 次方除以 C 的餘數 )


MsgBox A ^ B Mod C

A^B Mod C 通常如果在小數字的情況下可能會直接利用函數解決，但當遇到數字過大時通常都會產生溢位的狀況

那麼該怎麼解決呢?

通常第一個想法就是先實作一個大數次方 ( 迴圈+大數乘法 ) 然後在一個大數除法除到次方完 < C 也是一種作法

但是太累了！

有沒有更好的辦法 ?

有 ! 那就是每當 A * B 一次時就先開始 Mod C 取餘數


    Temp = A
For I = 1 To B - 1
    Temp = Temp * A
    Temp = Temp Mod C
Next I
    MsgBox Temp

但是當數字更大時 Temp Mod C 就會產生溢位

那該怎麼解決呢 ?

竟然沒辦法用 Mod 那我就用減法！


    Temp = A
For I = 1 To B - 1
    Temp = Temp * A
    Do Until Temp < C
        Temp = Temp - C
    Loop
Next I
    MsgBox Temp

看來已經解決了！但是速度似乎有點慢..因為一次只 - C 那我們可以怎麼去優化它呢?


    Temp = A
For I = 1 To B - 1
    Temp = Temp * A
    Do Until Temp < C
        If Temp - C * 100000 > C Then
            Temp = Temp - C * 100000
        ElseIf Temp - C * 10000 > C Then
            Temp = Temp - C * 10000
        ElseIf Temp - C * 1000 > C Then
            Temp = Temp - C * 1000
        ElseIf Temp - C * 100 > C Then
            Temp = Temp - C * 100
        ElseIf Temp - C * 10 > C Then
            Temp = Temp - C * 10
        Else
            Temp = Temp - C
        End If
    Loop
Next I
    MsgBox Temp

目前小弟只有想到這個方法，有更好方法的大大們歡迎提供共享︿︿

#0xDe 從分享中學習

#Facebook：ProgrammerDe (https://www.facebook.com/MicrosoftDes) 有問題歡迎提問

回首頁