经典算法 a^b

原题目链接

问题描述

求 a 的 b 次方对 p 取模的值，即计算：

a^b mod p

---

输入格式

输入一行，包含三个整数 a、b 和 p，中间用空格隔开。

---

输出格式

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

---

数据范围

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

---

输入样例

3 2 7

---

输出样例

2

c++代码

#include<bits/stdc++.h>using namespace std;typedef long long ll;ll mypow(ll a, ll b, ll p) {if (b == 0) return 1 % p;if (b == 1) return a % p;__int128_t k = mypow(a, b / 2, p);if (b % 2 == 0) return (k * k) % p;else return (k * k * a) % p;
}int main() {long long a, b, p;cin >> a >> b >> p;cout << mypow(a, b, p);return 0;
}//by wqs