初学快速幂 — 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^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);
}

]]>