[数据结构与算法-05]快速幂

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[数据结构与算法-05]快速幂，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1302字，纯文字阅读大概需要2分钟。

内容图文

快速幂

思路

• 分解：

\[7^{(1010100)_2} = (7^2)^{(101010)_2} = (7^4)^{(10101)_2} = (7^8)^{(1010)_2}*7^8 \]

• 利用位运算求\(b^p\)：
  • 不断把指数向右移位，b&1取得最后一位：
  • 每次右移相当于b/2，因此移完后将底数乘二
  • 若最后一位为1，答案要额外乘上b弥补整除带来的损失
• 若要求模，可在运算过程中取模，不影响最终结果

代码实现

long long quickPow(long long b, long long p, long long mod) {
	long long ans = 1;
	while (p) {
		if (p & 1)ans = ans * b % mod;
		b = b * b % mod;
		p = p>>1;
	}
        // 注意此处取模
	return ans % mod;
}

---

P1226 【模板】快速幂||取余运算

题目描述

给你三个整数 b,p,kb,p,k，求 b^p \bmod kb**pmodk。

输入格式

输入只有一行三个整数，分别代表 b,p,kb,p,k

输出格式

输出一行一个字符串 b^p mod k=s，其中 b, p, kb,p,k 分别为题目给定的值， ss 为运算结果。

输入输出样例

输入 #1复制

2 10 9

输出 #1复制

2^10 mod 9=7

说明/提示

样例输入输出 1 解释

2^{10} = 1024210=1024，1024 \bmod 9 = 71024mod9=7。

数据规模与约定

• 对于 100%100% 的数据，保证 0\le b,p < 2^{31}0≤b,p<231，1 \leq k \lt 2^{31}1≤k<231。

完整解答

#include <cstdio>
long long b, p, k;
long long quickPow(long long b, long long p, long long mod) {
	long long ans = 1;
	while (p) {
		if (p & 1)ans = ans * b % mod;
		b = b * b % mod;
		p = p>>1;
	}
	return ans % mod;
}
int main() {
	while (~scanf_s("%lld%lld%lld", &b, &p, &k)) {
		printf("%lld^%lld mod %lld=%lld\n", b, p, k, quickPow(b, p, k));
	}
	return 0;
}

内容总结

以上是互联网集市为您收集整理的[数据结构与算法-05]快速幂全部内容，希望文章能够帮你解决[数据结构与算法-05]快速幂所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---