分治法 —— 快速幂&取余运算

快速幂

关于快速幂的问题其实很早之前就已经遇到过了，但是当时怎么说呢？天真单纯，涉世不深（就是傻），只是一味地想着直接用循环去直接乘（越说越觉得自己是个傻子）。

直接进入正题：
所谓快速幂运算，就是将大幂转小幂，就是 a^x=a^{x_1+x_2},而这里用的分解方法是二进制的，如(11)_{10}=(1101)_2，其中11=8+2+1。为什么这么分，是因为a*a=a^2,a^2 * a^2 = a^4….,这样划分本来要做11次的乘法，直接简化为6次乘法。而在次数更高的情况下，简化的效果更明显。

这里要用一个与运算和移位运算，还是上面的例子。1101 & 0001 =0001，即其第一位有1的出现，则要乘以其一次方，再一位 1101变成110，在与1相与，以此类推。

上代码：

ll quickpower(ll a, ll b)     //快速计算a^b
{
    ll ans = 1;
    ll temp = a;
    while (b > 0)
    {
        if (b & 1)
            ans *= temp;
        temp *= temp;
        b >>= 1;
    }
    return ans;
}

取余运算

取余运算就很基础了，但鄙人想说的是将快速幂鱼取余运算结合
首先先看一下取余运算的运算规则：

(A+B) mod C=(A mod C+B mod C) mod C
(A*B) mod C=(A mod C * B mod C) mod C

上代码：

ll quickpower_mod(ll a, ll b, ll c)
{
    ll ans = 1;
    ll temp = a;
    while (b)
    {
        if (b & 1)
        {
            ans *= temp;
            ans %= c;
        }
        temp *= temp;
        temp %= c;
        b >>= 1;
    }
    return ans % c;
}

完整代码来一波

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;

ll quickpower(ll a, ll b)     //快速计算a^b
{
    ll ans = 1;
    ll temp = a;
    while (b > 0)
    {
        if (b & 1)
            ans *= temp;
        temp *= temp;
        b >>= 1;
    }
    return ans;

}

ll quickpower_mod(ll a, ll b, ll c)
{
    ll ans = 1;
    ll temp = a;
    while (b)
    {
        if (b & 1)
        {
            ans *= temp;
            ans %= c;
        }
        temp *= temp;
        temp %= c;
        b >>= 1;
    }
    return ans % c;
}



int main()
{
    ll a, b, c, ans;
    cin >> a >> b>>c;
    ans=quickpower_mod(a, b, c);
    cout << a << '^' << b << " mod " << c << '=' << ans;
    return 0;

}

打完收工