快速幂模板(luogu P1226 【模板】快速幂||取余运算)
程序员文章站
2022-05-14 17:17:51
...
题目描述
输入b,p,k的值,求b^p mod k的值。其中b,p,k*k为长整型数。
输入输出格式
输入格式:
三个整数b,p,k.
输出格式:
输出“b^p mod k=s”
s为运算结果
k*k为长整型,所以要想直接for循环你就凉飕飕,高进度写的脑阔又疼,下面就介绍一个神奇的算法,快速幂!!
如210,可以将10分成二进制下的1010,即210=(2(2^1))(2(23))=2228=210;
所以任意一个十进制数都可以转化成二进制数,对于a^b,可以将b拆分为二进制的数并逐步运算,可以在log n 下完成,非常快!!
话不多说,直接上代码。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int a,b,m;
int quickPow(int a,int b,int m){
int sum=1;
while(b){
if(b&1) sum=sum*a%m;
b>>=1;
a=a*a%m;
}
return sum;
}
int main(){
scanf("%d%d%d",&a,&b,&m);
printf("%d\n",quickPow(a,b,m));
return 0;
}
不理解的地方动手模拟一下代码,应该非常好理解
点个赞啦谢谢!!
上一篇: 虚拟机安装与网络配置
下一篇: BERT笔记