快速乘学习笔记

所谓快速乘实则是防止乘法越界而设计的算法。
模仿快速幂可得到 \(\operatorname{O}(\log n)\) 的（龟速）乘法：

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

运用 long double 特性可得到 \(\operatorname{O}(1)\) 的真·快速乘：

inline long long multi(long long a,long long b,long long mod)
{
    long long res=a*b-(long long)((long double)a/mod*b+0.5)*mod;
    return res<0?(res+mod):res;
}

快速乘学习笔记

原文：https://www.cnblogs.com/Psephurus-Gladius-zdx/p/12535539.html