[問題] Powering a number

[QwQxError (Satelliate)]

最近在用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
→ Richun: N^K = (q*M+N%M)^K = nM + (N mod M)^K 可能連大數都不用
→ stimim: N^(2K) = (N^K)^2,  N^(2K+1) = N * (N^K)^2
推 Sylveon: 用快速冪
花了一點時間
終於弄懂快速冪了
謝謝上面三位的回應
不過如果發生溢位 該怎麼處理？
※ 編輯: QwQxError (124.6.6.39), 06/21/2016 20:28:04
→ johnjohnlin: unsigned long long n2 = n, res = 1;
→ johnjohnlin: while(k){if(k%2)res=res*n2%m;res=res*n2%m;k/=2;}
→ johnjohnlin: ↑這樣