快速幂

对于一个 , 我们可以把它分为
如果化为二进制，则底数为a，指数为0或者1乘以2的次方的权重。
我们不妨举例一个例子

等价转换为

二进制数每位权重等于前一位自乘一次。任意进制数也一样。
故而我们可以看到，可以将指数按部分解，并且可以看到可以是10进制，也可以说是任意n进制。为了简化，我们将其化为二进制。故而每次计算出最后一项，只要先取n&1 看末尾数是不是1，如果是1，则乘上底数，如果不是，则部乘上底数。每次做完之后n=n>>1。

代码如下。

#include<cstdio>
int power(int a,int n){
    int p = a;
    int pow = 1;
    while( n > 0 ){
        if( n & 1)
            pow *=p;//如果末尾是1，就累乘以上去
        p*=p;//每一位的底数，指数为2次方权重
        n = n>>1;
    }
    return pow;
}
int main()
{
    int a,n;
    a = 2;
    n = 10;
    printf("%d\n",power(a,n));
    return 0;
}