[数据结构与算法]算法竞赛进阶指南打卡系列 0x00 1.a^b

算法竞赛进阶指南打卡系列题解

题目

原题链接

AcWing 89. a^b

题面

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

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

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

数据范围
$0\le a,b\le 10^9$
$1\le p\le 10^9$

输入样例：
3 2 7

输出样例：
2

题解

思路

快速幂 板子，直接抄就行了，注意在快速幂初始化时记得取模。

代码

#include <bits/stdc++.h>

// #define int long long

#define x first
#define y second

using namespace std;

typedef long long LL;

int 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;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b, p;
    cin >> a >> b >> p;

    cout << qmi(a, b, p) << "\n";

    return 0;
}