知识点：快速幂

递归公式（分治思想）：

$x^y=(x^{\lfloor\frac{y}{2}\rfloor})^2\cdot x^{y-2\cdot{\lfloor\frac{y}{2}\rfloor}}$，而终止条件为 $y=0$，此时 $x^y=1$。

即：

$x^y=\begin{cases} (x^{\frac{y}{2}})^2\qquad(2\mid y)\\ (x^{\frac{y-1}{2}})^2\cdot x(2\nmid y)\\ 1\qquad\qquad(y=0) \end{cases}$

代码如下：

int qpow(int a,int b){//即a^b
    if(b==0) return 1;//终止条件
    else if(b%2==0){
        int k=qpow(a,b/2);
        return k*k%MOD;
    }
    else{
        int k=qpow(a,b/2);
        return k*k%MOD*a%MOD;
    }
    //分治思想
}

我曾经写过一个及其精彩的错误代码：

int qpow(int a,int b){//即a^b
    if(b==0) return 1;//终止条件
    else if(b%2==0){
        return qpow(a,b/2)*qpow(a,b/2)%MOD;
    }
    else{
        return qpow(a,b/2)*qpow(a,b/2)%MOD*a%MOD;
    }
    //分治思想
}

本代码有什么问题？（设问的修辞手法）

答：这里。

return qpow(a,b/2)*qpow(a,b/2)%MOD;

以及：

return qpow(a,b/2)*qpow(a,b/2)%MOD*a%MOD;

这里相当于计算了两次qpow(a,b/2)。

所以需要乘 $b$ 次 $a$。

那么此“快速”幂的复杂度为 $O(b)$。

真正的快速幂的复杂度约为 $O(\log{b})$

用上面的那个即可通关。