算法：快速幂()

思想

快速幂的思想其实很简单，数学告诉我们，\(2^7\) 可以写成：

$ 24·22·2^1 $

观察上式，不难发现，任何数的任意次方可以拆分成若干个二的不同次方次相乘。

据此我们对原指数进行二进制拆分，根据其每一位上 \(1\) 的有无，来判断是否作幂。

实现

代码（不保证正确性）：

int fast_mi(int a,int n){
    int ans=0;
    while(n){
        if(n&1){
            ans+=a;  
        }   
        a*=a;
        n>>=1; 
    }
    return ans;
}
————————

思想

快速幂的思想其实很简单，数学告诉我们，\(2^7\) 可以写成：

$ 24·22·2^1 $

观察上式，不难发现，任何数的任意次方可以拆分成若干个二的不同次方次相乘。

据此我们对原指数进行二进制拆分，根据其每一位上 \(1\) 的有无，来判断是否作幂。

实现

代码（不保证正确性）：

int fast_mi(int a,int n){
    int ans=0;
    while(n){
        if(n&1){
            ans+=a;  
        }   
        a*=a;
        n>>=1; 
    }
    return ans;
}