快速幂

前几天有人想来这拿逆元的代码，然后没找到还鄙视我。被我回了一句你快速幂和拓欧都不会打么，然后他说不懂使用姿势……
其实我觉得我讲得够清楚了……一定是那家伙理解能力有问题……
那我就想为了方便这种懒人干脆就把这些基础全都写出来算了……
然后发现要我明确说出所以然还是挺困难的……还好想了一会儿想懂了……不过拓欧还没懂……

快速幂是能用来在$ O(\lg n) $的时间内求出$ a^n $的值。
首先我们知道，只用二的幂次方的数（以下简称二的幂）的和是能够表示所有正整数的，这即是二进制。
所以就能把这样的$ n $分解成二进制，或者说分成$ 2^0+2^1+2^2+ \cdots$（当然不是每一个幂都有）。
所以只需要让$ a $每次反复乘以自身（$ a^n \to a^{2n} $），在需要当前幂时再把之乘入到最终答案里。
具体来说的话将$ n $二进制分解后从后往前看，当前位若为$ 1 $则乘，否则罢了。
复杂度显而易见是$ O(\lg n) $。

代码

template<class T>
T power(T a, T n, T P)
{
    T ans = 1;
    while(n > 0)
    {
        if(n & 1)
            ans = ans * a % P;
        a = a * a % P;
        n >>= 1;
    }
    return ans;
}