博客

*纪念下AC的第一道快速幂类型题……大佬勿喷，欢迎指出错误。*



这道题题目大概是说，给你 b,p,k三个数，请你求出b^p mod k的值。

身为一名资深蒟蒻，习惯性的想到了朴素做法：

for（int i=1;i<=p;i++)
    ans=((ans%k)*(ans%k))%k;
cout << ans << endl;

但是，仔细一想，发现这道题完全可以使用快速幂来解决。

快速幂大概就是将a^b中的b转换为二进制，然后用O(log2n)的复杂度算出ans，具体请见下面的例子：

以题目样例 2^10 mod 9来举例子

10也就是二进制中的1010，于是2^10可以转化为：


2^(2^1)*2^(2^3)

那么同理，a^10可以转化为:


a^(2^1)*a^(2^3)

于是，a^b就可以转化为：b在二进制中若第i位为1，那么a*=a^(2^(i+1)),由于要考虑mod k，所以代码如下：

int getpaw(int a,int b)
{
    long long l=a,ans=1; //l为当前a^(2^i)的值
    while(b>0)
    {
        if(b&1!=0)//b是否不为0，否则ans就等于0，会造成答案错误
            ans=ans*l%k;
        l=l*l%k;//l自动变成下一位a^(2^i)的值
        b>>=1;//求b的二进制当前的最末位
    }
    return ans%k;   
}

最后附上这道题题解：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

long long b,p,k;

int paww(int a,int b)
{
    long long l=a,ans=1;
    while(b>0)
    {
        if(b&1!=0)
            ans=ans*l%k;
        l=l*l%k;
        b>>=1;
    }
    return ans%k;   
}

int main()
{
    cin >> b >> p >> k;
    cout << b << "^" << p << " mod " << k << "=" << paww(b,p) << endl;
}