快速幂+慢速乘

声明：转载请附上出处

先附上代码

long long multi(ll a,ll b,ll p)
{
    long long ans = 0;
    while (b)
    {
        if (b & 1)
        {
            ans = (ans %p+ a % p)%p;
        }
        b >>= 1;
        a = a * 2 % p;
    }
    return ans;
}
long long fast(ll a, ll b, ll p)
{
    long long ans = 1;
    while (b)
    {
        if (b & 1)// 我是11111111111111
        {
            ans = multi(ans, a, p);
        }
        b >>= 1;    
        a = multi(a, a, p);
    }
    return ans;
}

求
直接写快速幂就会爆long long 因为我们的p>1e9 假设在1处 我们ans为1e10 a也是1e10 那么相乘就爆了long long，所以我得用另外一种特殊的乘法 名为“慢速乘”。

慢速乘介绍

慢慢地将乘法运行，逼近模数的分界点，这里画个图。

因为a b都在mod的下面，所以乘的时候，我们让a一点点的去乘b，b“冒头”了一点，就取mod消除他。
（有点形象哈哈哈哈）

比如说4×5（a×b）%8
我们拆分为 2×（2×5） =2*2 -> 1×(2×2%12)//一直用两倍去乘他
当然 如果a是奇数，我们如同快速幂一样的处理就好了，加到我们的ans之中！

慢速乘板子

ll mult(ll a, ll b, ll p) 
{
   ll ans = 0;
    while (a)
    {
        if (a&1) { ans += b; ans %= p; }
        (b <<= 1) %= p;
        a >>= 1;
    }
    return ans;
}