[数据结构与算法]快速（模）幂计算

对于求a的b次方这种问题，直接计算肯定会比较慢，这时候就可能会用到快速幂的操作。

举个例子简单说一下：

????????比如求2的8次方，你可以看成8个2相乘，同时也可以看成4个4相乘，还可以看成是2个16相乘。可以看到，我在不断地将相乘的数扩大，而这个不断地将相乘的数变大的过程，也正是快速幂的精髓。剩下的，就交给代码了：

快速幂函数： 求a的b次方

//将无符号长整型定义为ll
typedef unsigned long long ll;
ll Power(ll a, ll b)
{
    ll res = 1;    //初始化结果为1
    //当指数不为0时继续计算
    while(b)
    {
        if(b % 2 == 1) { res *= a; }
        //将底数a扩大，指数b减半
        a *= a;
        b /= 2;
    }
    return res;
}

? ????????至于快速模幂，其实就是在每一步计算后多了一次模除，主要是为了防止幂运算后数据太过庞大而出现各种问题。

typedef unsigned long long ll;
ll Power(ll a, ll b, ll mod)
{
    //函数多传入一个要模除的数mod
    ll res = 1;
    while(b)
    {
        if(b % 2 == 1){ 
            res *= a; 
            res %= mod; 
        }
        a *= a;
        a %= mod;
        b /= 2;
    }
    return res;
}