[問題] 模指數運算
開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
dev C++
問題(Question)：
最近老師出了個程式作業要我們寫 模指數 b^n mod m 的運算
目前我想到的辦法是用char 陣列讀入輸入檔的數字 (有 被除數 被除數的次方 除數 )
將char 中的數字轉成整數後利用餘數次方的性質瘋狂的做減法運算
(就是 n^2 mod m 的餘數 = n mod m 餘數的平方)
不過感覺效率很差, google 後有找到這些方法
http://aoowweenn.blogspot.com/2009/03/blog-post.html
只是看太懂這些性質, 想請問板上大大有沒有其他方法可以提示一下
讓我可以思考還有什麼性質以及方法可以用, 謝謝 <(_ _)>
餵入的資料(Input)：
舉例來說
被除數 被除數次方 除數
123907862318756327 429867046 2208410817
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 58.114.32.225
→
10/10 13:37, , 1F
10/10 13:37, 1F
不太懂@@a 可以麻煩再解釋嗎?
→
10/10 15:02, , 2F
10/10 15:02, 2F
→
10/10 15:03, , 3F
10/10 15:03, 3F
→
10/10 15:03, , 4F
10/10 15:03, 4F
→
10/10 15:10, , 5F
10/10 15:10, 5F
→
10/10 15:11, , 6F
10/10 15:11, 6F
謝謝t 大. 不過不知道有沒有可以把數字拆開算的方法?
比方20位數可以拆成前面10位跟後面10位來看
否則好像還要寫個自訂class 來解決@@a 謝謝
※ 編輯: JiMor 來自: 58.114.32.225 (10/10 16:20)
→
10/10 17:25, , 7F
10/10 17:25, 7F
→
10/10 23:13, , 8F
10/10 23:13, 8F
→
10/10 23:13, , 9F
10/10 23:13, 9F
因為老師給的測試檔超過20位數, 所以才想問有沒有其他辦法
→
10/10 23:45, , 10F
10/10 23:45, 10F
另外刻是什麼意思? 小弟還是個菜鳥, 不太懂@@a
→
10/10 23:47, , 11F
10/10 23:47, 11F
→
10/10 23:48, , 12F
10/10 23:48, 12F
→
10/10 23:48, , 13F
10/10 23:48, 13F
我現在實做是宣告一個 int array[40], 裡面只放數字 0~9
然後昨晚把大數除法寫完, 測試發現如果數字在一定的範圍內算出的餘數沒問題
但是數字很大的話...... 結果會跟小算盤算出來的不同QQ
感覺我好像寫錯了= =
※ 編輯: JiMor 來自: 140.115.170.206 (10/11 19:31)
→
10/11 19:43, , 14F
10/11 19:43, 14F
→
10/11 21:02, , 15F
10/11 21:02, 15F
嗯...... 我盡量努力QQ
題外話問一下, 想請問 t大PO的頁面中, Montgomery 那段code 有個
p >>= 1 是什麼意思
※ 編輯: JiMor 來自: 140.115.50.29 (10/13 13:54)
→
10/13 14:33, , 16F
10/13 14:33, 16F
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
