一般的快速幂并不适合模数大于int范围的情况，因为在乘法运算的过程可能会出现超出long long的情况出现。这个时候可以利用快速幂的思想使用快速乘，原理就是模拟乘法运算，将乘法运算分解成加法运算，再每次加的时候取模，具体实现类似快速幂，代码如下：
LL M; LL qmul(LL a,LL b){ LL ret=0; while(b){ if(b&1) ret=(ret+a)%M; b>>=1; a=(a+a)%M; } return ret; } LL qpow(LL a,LL b){ LL ret=1; while(b){ if(b&1) ret=qmul(ret,a); b>>=1; a=qmul(a,a); } return ret; }
原文：https://www.cnblogs.com/FrankChen831X/p/10809399.html