《a^b》 题解，dalao们不喜勿喷 首先，关于这道题，我要好好说道说道

这道题我看了这道题很多人的状态就只得了60分。第一眼我的感觉是这道题太简单了，直接定义三个变量a,b,p，再pow(a,b)%p完事。代码如下

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,p;
    cin>>a>>b>>p;
    int c = pow(a,b);
    cout<<c%p;
}

结果发现，也只得了六十分，样例4 5 不过......。于是，我对这道题进行了长达三周的死磕

。近几天，我在备考CSP—J初赛的时候，看到一道补全代码题。名字就叫《快速幂》，题目的描述也算是给了我一些提示

其中一句话：若p为偶数，x^p = ( x^2 )^p/2; 若p为奇数，x^p=x* ( x^2 )^(p-1)/2。

意思也就是：底数平方，指数减半。如果指数是一个奇数，那么就指数减一后再减半，把减去的那一次再乘到底数里

于是，我就兴高采烈地把那个代码写了过来，代码如下

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long  a,b,p;
    cin>>a>>b>>p;
    long long  result = 1;
    while(b>0)
    {
        if(b%2==1)
        {
            result = (result*a)%p;
        }
            b = b/2;
            a = (a*a)%p;
    }
    cout<<result;
}

但是结果显示，八十分。此时此刻我快要崩溃了，样例三不过。报错信息：Wrong Answer 0 读取到 1，应为 0。这个代码问题在于如果输入a^b(a,b均为任意数)%1的时候，输出结果却都是一，所以。还要做一一个判断，再输出

if(p==1)
    {
        cout<<0;
    }
    else
    {
        cout<<result;
    }

所以，完整代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long  a,b,p;
    cin>>a>>b>>p;
    long long  result = 1;
    while(b>0)
    {
        if(b%2==1)
        {
            result = (result*a)%p;
        }
            b = b/2;
            a = (a*a)%p;
    }
    if(p==1)
    {
        cout<<0;
    }
    else
    {
        cout<<result;
    }
}

dalao们重点加粗的字看一下就行了，剩下的全是废话。普通解法的时间复杂度是O(1),但只适用于极小的b,b<=20;快速幂时间复杂度是O(log b)。

最重要的强调一下，1.判断 2.一定要开long long