最近在用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;}↑这样