快速幂取模

long long quick_mod(long long a,long long b,long long Mod)
{
long long ans = 1;
a %= Mod; //对刚进来的a进行取模运算，避免后面第一次求平方运算溢出
while(b)
{
if(b&1) //对二进制下的 b 进行按位与1运算，求二进制下 b 的最低位是否为1
ans = ans * a % Mod; //对结果进行保存
b>>=1; //二进制下的 b 右移一位，相当于十进制下的 b 除以2
a = a * a % Mod;
}
return ans % Mod;
}

快速幂取模

原文：https://www.cnblogs.com/RainzzZ/p/12109453.html