快速(模)幂

快速幂

原理：把超多次乘法转换为少次乘法

比如求2的8次方，你可以看成8个2相乘，同时也可以看成4个4相乘，还可以看成是2个16相乘。
可以看到，通过递归，不断地将相乘的数扩大，而这个不断地将相乘的数变大的过程，也正是快速幂的精髓。

//将无符号长整型定义为ll
typedef unsigned long long ll;
ll Power(ll a, ll b)
{
    ll res = 1;    //初始化结果为1

    while(b)//当指数不为0时继续计算
    {
        if(b&1) { res *= a; }//不恰好可以让指数÷2，就先乘个a
        //将底数a扩大，指数b减半
        a *= a;
        b>>= 1;
    }
    return res;
}

快速模幂

原理：数学运算将mod提取入底数，加快运算速度(?)

$10^{4}$ mod6可以转变为($10^{2}+10^{2})mod6$,可以变化为$(10^{2}mod6)(10^{2}mod6)$,同样的操作最后就变为$(10mod6)^{4}mod6$(一边次方一边模)

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