牛客-996A a^b（快速幂）

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

题目描述

求 a 的 b 次方对 p 取模的值，其中 $0 \leq a,b,p \leq 10^9$

输入描述:

三个用空格隔开的整数a,b和p。

输出描述:

一个整数，表示$a^b \bmod p$的值。

示例1

输入

2 3 9

输出

8

---

#include <bits/stdc++.h>

using namespace std;

long long calculate(long long a, long long b, long long p)
{
    if (a == 0) return 0;

    long long res = 1 % p;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }

    return res;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long a, b, p;
    cin >> a >> b >> p;

    cout << calculate(a, b, p) << endl;

    return 0;
}