快速幂C++实现

快速幂模板题

很明显,这个题目不能用简单的\(for\)循环+\(mod\)来完成,因为指数\(p\)已经达到了长整型,直接循环来完成的话肯定会超时的。

那么快速幂就应运而生了.

什么是快速幂呢?

利用二进制扩大底数,减少计算次数,经常会涉及到到类似\(a^b\mod p\)的运算,这里的\(b\)常常会很大,导致我们不能\(for\)循环计算。

那么怎么用代码实现呢?

首先,为了保险我们把所有的数据类型都设置为long long

然后为了方便,把快速幂写作一个函数,参数就是上面提到的\(a,b,p\),这是个好习惯

快速幂顾名思义,就是快速算某个数的多少次幂。其时间复杂度为 O(logN),与朴素的O(N)相比效率有了极大的提高。

简单来说,就是个二分求模的过程。

至于二分过程,无非就是扩大底数减少指数,达到降低时间复杂度的效果。

但要注意的是,因为快速幂普遍会有一个取模操作,所以在过程中就要进行\(mod\)哦。

代码也很简单,就以自定义函数的方式贴下面吧...

long long qpow(long long a,long long b,long long p)
{
        long long x=a;
        long long ans=1;
        while(b)
        {
                if(b%2!=0)
                        ans*=x;
                ans%=p;
                x*=x;
                x%=p;
                b/=2;
        }
        return ans;
}

ov.