快速幂取模算法 | Justin博客

算法位运算

算法

发布日期: 2019-05-03

文章字数: 583

阅读时长: 2 分

阅读次数:

引言

快速幂的目的就是做到快速求幂，假设我们要求a^b,按照朴素算法就是把a连乘b次，这样一来时间复杂度是O(b)也即是O(n)级别，快速幂能做到$O(log_{2}b)$。

题目

求a的b次方对p取模的值,其中1<=a,b,p<=10^9

思路分析

根据数学常识，每一个正整数都可以唯一表示为若干指数不重复的2的次幂的和。也就是说，如果b在二进制下有k位，其中i(0<=i<k)位的数字
是ci，那么：

$$b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+c_{k-3}2^{k-3}+…+c_{0}2^{0}$$

于是有：

$$a^{b}=$a^{c_{k-1}2^{k-1}}*a^{c_{k-2}2^{k-2}}*a^{c_{k-3}2^{k-3}}*…*a^{c_{0}2^{0}}$$

因为k=$log_{2}(b+1)$向上取整,所以上式乘积项的数量不多于k个，又因为：

$$a^{2^i}=(a^{2^{i-1}})^2$$

所以，我们很容易就可以通过k次递推求出每个乘积项

当$c_{i}=1$时，把该乘积项累积到答案ans中
b&1 运算可以取出b在二进制表示下的最低位
而b>>1运算可以舍去最低位，在递推公式过程中，1和2结合，就可以遍历b在二进制表示下所有数位$c_{i}$

该算法复杂度为 $O(log_{2}b)$

算法实现

实现一

int power(int a,int b,int p)&#123;
    int ans = 1%p;
    for(:b ;b>>=1)&#123;
        if(b&1) ans = (lonog long)ans*a%p
        a = (long long)a * a %p;
    &#125;
    return ans
&#125;

实现二

#include <iostream>
using namespace std;
typedef unsigned long long ULL;//防止溢出
int main()&#123;
    ULL a,b,p;
    ULL ans=0;
    cin>>a>>b>>p;
    while(b)&#123;
        if(b&1) res=res*a%p;
        a=a*a%p
        b>>=1;
    &#125;
    count<<res<<endl;
    return 0;
&#125;