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/