1.快速幂 - 蓝桥云课

题目描述

输入 b，p，k 的值，求 bpmodk 的值。其中 2≤b,p,k≤109。

输入描述

三个整数 b,p,k。

输出描述

输出 bpmodk=s，s 为运算结果。

输入输出样例

示例

输入	输出
2 10 9	7

运行限制

• 最大运行时间：1s
• 最大运行内存：128M

总通过次数：4565 | 总提交次数：4964 | 通过率：92%

难度：中等 标签：快速幂，倍增，分治

思路：

模板

代码：

#include<iostream>
using namespace std;
typedef long long ll;
ll b,p,k;
ll qmi(ll m ,ll k ,ll p)
{ll res = 1 % p,t = m;while(k){if(k&1)res = res * t % p;t = t * t % p;k >>= 1;}return res;
}
int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> b >> p >> k;cout << qmi(b,p,k);return 0;
}