a^b

题目 a^b

思路分析

快速幂

将\(a^b\)中的b拆成二进制的每一位

利用预处理和递推 快速求出\(a^b\)

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int a,b,p;

LL qmi(int a,int b,int p)

{

    int res=1%p;

    while(b)

    {

        if(b&1)

            res=(LL)res*a%p;

        a=(LL)a*a%p;

        b>>=1;

    }

    return res;

}

int main()

{

    cin>>a>>b>>p;

    cout<<qmi(a,b,p);

    return 0;

}

同类题型

视频讲解

⬅️ 快速幂 🏠 00-刷题理模型 ➡️ 位运算