快速幂

快速幂

快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。

位运算版

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

ll inv(ll a,ll p)
{
	return qpow(a,p-2);
}

递归版

ll qpow(ll a,ll n)
{
    if(n==1) return a;
    ll temp=qpow(a,n/2);
    return (n%2==0 ? 1:a)*temp*temp;
}

ll inv(ll a,ll p)
{
	return qpow(a,p-2);
}