快速幂
2022/7/24 6:25:13
本文主要是介绍快速幂,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给定 \(n\) 组 \(a_i, b_i, p_i\),对于每组数据,求出 \(a_i ^ {b_i} \bmod p_i\) 的值。
快速幂算法
可以快速求\(a^b \% p\)的问题
思路
- 预处理\(a^{2^0},a^{2^1},a^{2^2}\dots,a^{2^{\log b}}\)
- \(b^a\)就可以用上述式子表示,比如\(3^{17}=3^{16}\times3^{1}=3^{2^{4}}\times3^{2^{0}}\)这样能把\(a^{2^0}+a^{2^1}+a^{2^2}\dots+a^{2^{\log b}}\)内的数都用二进制表示出来
码来!
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; LL quick_pow(int a, int b, int mod) { LL res = 1 % mod; // 当mod = 1时,res = 0 while(b) { if(b & 1) res = res * a % mod; // 当b的二进制位最小位为1时 b >>= 1; // 删掉最小位 a = a * (LL)a % mod; // 不(LL)会爆 } return res; } int main() { int n; scanf("%d", &n); while(n--) { int a, b, p; scanf("%d%d%d", &a, &b, &p); printf("%lld\n", quick_pow(a, b, p)); } return 0; }
这道题这个算法的时间复杂度是\(O(n \log b)\)
这篇关于快速幂的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?