[問題] Powering a number

看板C_and_CPP作者 (Satelliate)時間9年前發表 (2016/06/19 02:41), 9年前編輯推噓1(1推 0噓 5→)
留言6則, 4人參與, 最新討論串1/1
最近在用VC++14練習大數運算 題目內容： 依序輸入三個整數N、K與M， 輸出N的K次方用M除的餘數 也就是輸出 N^K mod M 我當時以為用大數乘法就可以 可是看到測資 感覺會迴圈到10億次 就認為不可能了 測資為： 1000007949 1000008723 1000020917 輸出答案： 477542316 想請問板上的各位有什麼解法嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.218.112.239 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1466304088.A.8CB.html
→
06/19 11:45, , 1F
N^K = (q*M+N%M)^K = nM + (N mod M)^K 可能連大數都不用
06/19 11:45, 1F
→
06/19 12:28, , 2F
N^(2K) = (N^K)^2, N^(2K+1) = N * (N^K)^2
06/19 12:28, 2F
推
06/19 13:35, , 3F
用快速冪
06/19 13:35, 3F
花了一點時間 終於弄懂快速冪了 謝謝上面三位的回應 不過如果發生溢位 該怎麼處理？ ※ 編輯: QwQxError (124.6.6.39), 06/21/2016 20:28:04
→
06/21 21:31, , 4F
unsigned long long n2 = n, res = 1;
06/21 21:31, 4F
→
06/21 21:32, , 5F
while(k){if(k%2)res=res*n2%m;res=res*n2%m;k/=2;}
06/21 21:32, 5F
→
06/21 21:32, , 6F
↑這樣
06/21 21:32, 6F
‣ 更多 QwQxError 的文章
文章代碼(AID): #1NPWPOZB (C_and_CPP)