AcWing:89. a^b

0x00 基本算法第一题

算法标签 :?位运算?快速幂

来源：《算法竞赛进阶指南》

描述

求?a?的?b?次方对?p?取模的值。

输入格式

三个整数?a,b,p,在同一行用空格隔开。

输出格式

输出一个整数，表示a^b mod p的值。

数据范围

0≤a,b≤10^9
1≤p≤10^9

输入样例：

3 2 7

输出样例：

2

?自用,AC代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int qsm(int a, int b, int p) // 快速幂,需熟记
{
    int res = 1 % p; // 与p取模
    for (; b; b >>= 1) // 无起始,终止条件是b == 0,每次去b的二进制下的末位
    {
        if (b & 1) // 判断b的末尾是0或1,是1就加
            res = res * 1ll * a % p; // 1ll 为强制类型转化,转成long long
        a = a * 1ll * a % p; // 无论b是否为1,a值还是要累乘的
    }
    return res;
}

int main()
{
    
    int a,b,p;
    scanf("%d %d %d", &a, &b ,&p);
    int res = qsm(a,b,p);
    printf("%d",res);
}

?