上海招聘用的最多的网站,北京seo外包,汕头模板自助建站,网站建设shundeit【题目来源】https://www.luogu.com.cn/problem/P1226【题目描述】 给你三个整数 a#xff0c;b#xff0c;p#xff0c;求 a^b mod p。【输入格式】 输入只有一行三个整数#xff0c;分别代表 a#xff0c;b#xff0c;p。【输出格式】 输出一行一个字符串 a^b mod psbp求 a^b mod p。【输入格式】 输入只有一行三个整数分别代表 abp。【输出格式】 输出一行一个字符串 a^b mod ps其中 abp 分别为题目给定的值s 为运算结果。【输入样例】 2 10 9【输出样例】 2^10 mod 97【说明/提示】 样例解释2^10 10241024 mod 97。 数据规模与约定对于 100% 的数据保证 0≤a,b2^31ab02≤p2^31。【算法分析】 ● 快速幂又称二进制取幂是一个以 的时间复杂度计算 的小技巧而暴力的计算需要 的时间复杂度。● 快速幂的原理 答快速幂的原理为“将求幂的任务按照指数 的二进制表示分割成更小的任务”。例如 因为 有 个二进制位因此当知道了 后我们只需计算 次乘法就可以计算出 。● 快速幂经典代码
#include bits/stdc.h
using namespace std;typedef long long LL;int fastPow(LL a,LL n) {LL ans1;while(n){if(n 1) ansans*a;n1;aa*a;}return ans;
}int main() {int a,n;cinan;coutfastPow(a,n)endl;
}/*
in:6 8
out:1679616
*/
● 带取模的快速幂代码 计算过程中为了防止溢出需要进行“取模”运算其运算规则如下(ab)%p(a%pb%p)%p (a-b)%p(a%p-b%p)%p (a*b)%p(a%p*b%p)%p【算法代码】
#include bits/stdc.h
using namespace std;typedef long long LL;int fastPow(LL a,LL b,LL p) {LL ans1;while(b){if(b 1) ansans*a%p;b1;aa*a%p;}return ans%p;
}int main() {int a,b,p;cinabp;couta^b mod pfastPow(a,b,p)%p;
}/*
in:2 10 9
out:2^10 mod 97
*/
【参考文献】https://www.cnblogs.com/littlehb/p/15588930.htmlhttps://oi-wiki.org/math/binary-exponentiation/
