初学快速幂 — CodeVS 3500 快速幂入门

快速幂

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^42^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);
}
]]>

加入对话

2条评论

留下评论

电子邮件地址不会被公开。 必填项已用*标注