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


快速幂是能用来在$ 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;
}

标签: none

添加新评论