快速幂运算and 快速乘运算

ll qpow(ll a,ll b)
{ll ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;
}

快速乘运算

ll mult(ll a,ll b,ll mod)
{a%=mod,b%=mod;ll s=a,sum=0;while(b){if (b&1){sum+=s;if (sum>=mod)sum-=mod;}b>>=1;s<<=1;if (s>=mod)s-=mod;}return sum;
}

相互结合:

ll mult(ll a,ll b,ll mod)
{a%=mod,b%=mod;ll s=a,sum=0;while(b){if (b&1){sum+=s;if (sum>=mod)sum-=mod;}b>>=1;s<<=1;if (s>=mod)s-=mod;}return sum;
}ll qpow(ll a,ll b)
{ll ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(mult(a,a))%mod;b>>=1;}return ans;
}