快速乘

快速乘

快速乘可以解决  A*B%mod  爆long long的问题

两种方法

O(1)复杂度

引用自2009年国家集训队论文，骆可强：《论程序底层优化的一些方法与技巧》

原文中用的double   做题的时候建议用long double(long double舍弃低位且范围保留18位)

typedef long long ll;
const int mod=1e9+7;
ll mul(ll a,ll b)
{
    ll c=(long double)a*b/mod;
    ll ans=a*b-c*mod;
    return   ans<0?ans+mod:ans;
}

O(logn)复杂度

上面那个O(1)的方法 快是快  但是用到了浮点运算  误差是不可避免的  mod太大的时候不建议使用

那么我们可以利用快速幂的思想来计算乘法

由于计算机底层设计的原因，做加法往往比乘法快的多，因此将乘法转换为加法计算将会大大提高（大数，比较小的数也没必要）乘法运算的速度，除此之外，当我们计算a*b%mod的时候，往往较大的数计算a＊b会超出long long int的范围，这个时候使用快速乘法方法也能解决上述问题．
快速乘法的原理就是利用乘法分配率来将a＊b转化为多个式子相加的形式求解（注意这时使用乘法分配率的时候后面的一个乘数转化为二进制的形式计算）．举个栗子
20＊14 ＝ 20＊(1110)2 = 20＊(2^3)＊1 + 20＊(2^2)＊1+20＊(2^1)＊１+20＊(2^0)＊0 = 160+80+40=280.
上面即为快速乘法的基本原理

代码

ll mul(ll a,ll b,ll mod) { 
    ll res = 0; 
    while(b){ 
        if(b&1)res=(res+a)%mod; 
        a = (a+a)%mod; 
        b >>= 1; 
    } 
    return res; 
}