AcWing 89：a^b ← 快速幂

【题目来源】
https://www.acwing.com/problem/content/91/

【题目描述】
求 a 的 b 次方对 p 取模的值。

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

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

【数据范围】
0≤a,b≤10^9
1≤p≤10^9

【输入样例】
3 2 7

【输出样例】
2

【算法分析】
● 单变量的快速幂：https://blog.csdn.net/hnjzsyjyj/article/details/143168167
● 矩阵的快速幂：https://blog.csdn.net/hnjzsyjyj/article/details/143227091

【算法代码】

#include <bits/stdc++.h>
using namespace std;typedef long long LL;LL fastPow(LL a,LL b,LL p) {LL ans=1;while(b) {if(b & 1) ans=ans*a%p;a=a*a%p;b>>=1;}return ans%p; //not return ans
}int main() {LL a,b,p;cin>>a>>b>>p;cout<<fastPow(a,b,p)<<endl;return 0;
}/*
in:
3 2 7out:
2
*/

【参考文献】
https://www.acwing.com/solution/content/788/