0x01 基本算法-位运算 a^b(快速幂)

链接：https://ac.nowcoder.com/acm/contest/996/A

  题意：求% mod 。
  思路： ,假设我们要求 那么我们可以转换成， 也就是 我们可以发现当 b 的二进制位的某一位是 1 时，我们需要做一个累乘 ans 的操作，否则我们需要 a 的指数乘 2 操作。这样的操作就是快速幂。 假设我们现在右有

using namespace std;

typedef pair<int,int> P;
typedef long long ll;
const int Max_n=2e5+10;

int q_pow(int a,int b,int mod){
    ll ans=1,res=a%mod;
    while(b){
        if(b&1) ans=ans*res%mod;
        res=res*res%mod;
        b>>=1;
    }
    return ans%mod;
}

int main(){
    int a,b,mod;
    scanf("%d%d%d",&a,&b,&mod);
    printf("%d\n",q_pow(a,b,mod));
    return 0;
}