【每日一题27】AcWing 89. a^b

发表于 更新于 分类于 Valine：
本文字数： 58 阅读时长 ≈ 1 分钟

Day27 AcWing 89. a^b

思路

  1. 快速幂算法

拓展

  1. 求A^B的最后三位数表示的整数

    求后三位 %1000 两位 %100

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>

using namespace std;

typedef long long LL;

int qmi(int a, int b, int p)
{
    int res = 1 % p; //模为1时 res=0
    while (b)
    {
        if (b & 1) res = (LL)res * a % p; //&与运算 b&1==0 偶数 / b&1==1奇数
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    int a, b, p;
    cin >> a >> b >> p;
    cout << qmi(a, b, p) << endl;
    return 0;
}