快速幂
Summary
快速幂（Binary Exponentiation）把指数按二进制拆分，每一步将底数自乘平方，遇到当前二进制位为 1 就把此时的底数乘入答案，于是只需 O(logy) 次乘法就能求出 x 的 y 次方模 p。龟速乘沿用同样的倍增思想计算 x 乘 y 模 p，把一次乘法拆成若干次取模加法，避免两个大数直接相乘时溢出。除龟速乘外，还给出两种更快的取模乘法：借助 128 位整数类型暂存乘积后取模，或用 long double 估出商、再修正回来的写法。文末以模板题作为例题。
参考资料
快速幂
快速幂（Binary Exponentiation）把指数 按二进制拆分，每一步将底数平方，遇到为 的二进制位就把当前底数乘入答案，从而在 内求出 。
ll Pow(ll x,ll y)
{
x%=mod;
ll res=1;
while(y)
{
if(y&1)res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
龟速乘
龟速乘用于计算 ，可以防止直接计算 过大导致溢出。
ll mul(ll x,ll y)
{
x%=mod;
ll res=0;
while(y)
{
if(y&1)res=(res+x)%mod;
x=(x+x)%mod;
y>>=1;
}
return res;
}
另外两种实现：
- __int128
- long double
ll mul(ll a,ll b,ll mod)
{
return __int128(a)*b%mod;
}
ll mul(ll a,ll b,ll mod)
{
return (a*b-ll(ld(a)/mod*b+0.5)*mod+mod)%mod;
}