题目描述

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

输入格式

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

输出格式

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

数据范围

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

样例

3 2 7

2

算法

(快速幂板子) $O(log(n))$

C++ 代码

#include <iostream>
using namespace std;

typedef long long LL;

int a, b, p;

LL qmi(int a, int k, int q) {
    LL ret = 1;
    while (k) {
        if (k & 1) ret = ret * a % q;
        k >>= 1;
        a = (LL)a * a % q;
    }
    return ret % q;
}

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