最近在用VC++14練習大數運算
題目內容：
依序輸入三個整數N、K與M，
輸出N的K次方用M除的餘數
也就是輸出 N^K mod M
我當時以為用大數乘法就可以
可是看到測資
感覺會迴圈到10億次
就認為不可能了
測資為：
1000007949
1000008723
1000020917
輸出答案：
477542316
想請問板上的各位有什麼解法嗎？

N^K = (q*M+N%M)^K = nM + (N mod M)^K 可能連大數都不用

N^(2K) = (N^K)^2, N^(2K+1) = N * (N^K)^2

用快速冪

unsigned long long n2 = n, res = 1;while(k){if(k%2)res=res*n2%m;res=res*n2%m;k/=2;}↑這樣