简介
快速幂求余算法是一种可以在O(logn)下求出ab mod c的一种算法。
具体实现
需要用到的定理：
上面的公式，使得原本需要用a的b次方才能取得的余数，现在远远小于b的次方就可以求得。
算法实现：
long long PowerMod (int a, int b, int c) { int ans = 1; a = a % c; while(b>0) { if(b % 2 = = 1) //b为奇数 ans = (ans * a) % c; b = b/2; // b>>=1; a = (a * a) % c; } return ans; }
原文：https://www.cnblogs.com/woxiaosade/p/10810084.html