快速幂
long long ans=1;
for(int i=1;i<=p;i++){
ans*=a;
ans%=k;
}
说起求幂,大多数时候,我们用的都是上面这个简单通俗易懂是人都会的暴力循环
但是时间还是相当难受的,譬如求2^2000000%100
,多来几次,你的时间就会很怎么优化?
2^n*2^m=2^(n+m)
这个东西大家都学过也都了解,那么我们今天就从这里优化
对于2^p
一定有2^p=2^(p/2)+2^(p/2)
比如2^8
我们可以拆成2^8=2^4*2^4
而2^4=2^2*2^2
,所以三次循环就可以算出原来要8次循环的运算,看起来是不是很合算~
CodeVS 3500 快速幂入门
题意就是纯属模板题木,不过千万不要忘记了要取模代码
#include <cstdio>
#include <cstring>
using namespace std;
long long a,b,c,ans=1;
int main(){
scanf("%lld%lld%lld",&a,&b,&c);
while(b>0){
if(b&1) ans=((ans%c)*(a%c))%c;
b>≥1;
a=(a*a)%c;
}
printf("%lld",ans%c);
}
]]>
那个…传统求幂运算中那个ans=0是个什么鬼,不是1吗
妈耶傻了傻了
已修正