普通的快速幂

问题：[COGS 1433]圣庙里的汉诺塔

计算$a^b\mod m$，其中$0\leq a,b\leq10^{16}$。

我们可以写出如下的暴力求幂程序，复杂度$O(n)$:

typedef long long ll;
ll pow_mod(ll a,ll b,ll m)
{
  	ll ans=1;
  	while(b--)
      	ans=(ans*a)%m;
  	return ans;
}

不过注意到对于任意正整数k，我们都可以拆成至多$log k$个二进制下的1,所以我们可以计算出$a^{2^0},a^{2^1},a^{2^2},\cdots$（可以递推出来）,然后再用$\log b$次乘法将其合并起来，复杂度为$O(\log n)$，代码如下：

ll fast_pow_mod(ll a,ll b,ll m)
{
    ll ans=1;
  	while(b)
    {
      	if(b&1)
          	ans*=a;
      	a*=a;
      	b>>=1;
    }
  	return ans;
}

由快速幂魔改的快速乘

问题：[COGS 2037]Asm.def大点兵

由于$a\times b$可能溢出，因此不能直接乘起来再取膜，考虑到一个事实： $$ a^b= \begin{cases}

1 & b=0 \\
\underbrace { a \times \cdots \times a }_b & b \ge 1

\end{cases} $$ $$ a\times b= \begin{cases} 0&b=0
\underbrace{a+\cdots+a}_b&b\not=0 \end{cases} $$ 所以我们把上面的代码稍微改一改就好了：