快速幂

今天的内容是快速幂，是编程中求幂的得力能手，一定要背下来哦。
注意：本篇对三目运算符做了一定的介绍。如果已对三目运算符有了解，可跳过“如何使用三目运算符”
讲解之前，别忘了收藏我的编程专题哦

做法

在求时，若为偶数，运算，否则运算。注意运算是不四舍五入的整除。

证明

这个证明没有什么难的.
假设是奇数，整除，那么是显而易见的。

image
例如：
偶数情况只是少了这个多余的而已，可自行证明一下。

区别

时间复杂度从变为 。假设我们已经有了和，且我们要求。
普通幂是这样实现的：

int ans=a;
int pow(int a,int n){
    for(int i=1;i<n;i++){
        ans*=a;
    }
}

此方法运行了次。
快速幂的写法是递归：

int pow(int a,int n){
    if(p==0)return;
    int t=pow(a,n/2);
    if(n%2==0){
        return t*t;
    }
    else{
        return t*t*a;
    }
}

如何使用三目运算符

实际上上面的代码就是正确的代码，但希望通过这篇博客，大家能认识一个新东西：三目运算符。
中惟一的三目运算符是这样写的：

(expression) ? (do something) : (do something else)

它相当于：

if(expression)
    do something;
else
    do something else;

那么为什么使用此运算符呢？因为它短小精悍。当然，如果后面有多句话，就不提倡这么做了。

• 经典的用三目运算符的例子：

int compare_which_bigger(int a,int b){
    a>b ? return a : return b;
}

• 经典的反面例子：

int compare_which_biggest(int a,int b,int c,int d,int e){
    a>b||a>c||a>d||a>e ? return a : (b>c||b>d||b>e||b>a ? return b : (c>a||c>b||c>d||c>e ?return c : (d>a||d>b||d>c||d>e ? return d : return e)));
}

快速幂最终代码

int pow(int a,int n){
    if(p==0)return;
    int t=pow(a,n/2);
    n%2==0 ? return t*t : return t*t*a;
}