快速幂

原理

例如,其实指数b可以拆成二进制。通过公式。可以发现,一旦指数b拆成二进制,那么也可以进行相应的拆分。

例如,当b=11时,b的二进制为1011,即

那么

接着就是判断一个数字二进制形式的某个位置是0还是1。

使用位运算符

  1. &运算:通常用于二进制取位操作,例如一个数x & 1 的结果就是取二进制的最末位的值。还可以判断这个数的奇偶性,如果x&1==0,则x为偶数;如果x&1==1,则x为奇数。
  2. >>运算:在这里是作为除法来使用,例如一个数x,x >> 1就表示x右移一位,即x=x/2。

代码

#include<bits/stdc++.h>
using namespace std;
int pow(int a,int b){
    int ans = 1,base = a;//ans是结果,base是底数 
    while(b){
        if(b&1){    //判断奇偶性
            ans*=base;
        }
        base*=base;
        b>>=1;//右移一位,相当于除2
    }
    return ans;
}
int main(){
    int a,b;
    cin>>a>>b;
    cout<<pow(a,b)<<endl;
    return 0;
} 

快速幂取模

原理

主要依赖取模运算的公式

代码

#include<bits/stdc++.h>
using namespace std;
int pow(int a,int b,int c){
    int ans = 1,base = a;//ans是结果,base是底数
    base %= c;
    if(b==0){
        return 1%c; //零次幂返回1
    }
    while(b){
        if(b&1){ //判断奇偶性
            ans = (ans*base)%c;
        }
        base = (base*base)%c;
        b>>=1; //右移一位,相当于除2
    }
    return ans;
}
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    cout<<pow(a,b,c)<<endl;
    return 0;
} 

一只小菜鸡