FastDivFastMod_杂项

FastDiv/FastMod

假：

原理：

inv[i]=-1ull/i+1,a/b==(i128)a*inv[b]>>64,a%b==a-a/b*b

所以在输入模数的情况下可以加速取模。

struct FastMod {
    using ull=decltype(1ull);
    ull p,m;
    FastMod(ull p):p(p),m(-1ull/p+1) {}
    ll operator()(__int128 x) {
        return x-(x*m>>64)*p;
    }
};

得到这个做法的时候很欣喜，殊不知这是假的，用它处理阶乘的逆元 $\frac 1{16!}$ 就会出现负数，经过群友分析该算法会将答案映射到 $[-p,p)$，而正常的巴雷特模乘会映射到 $[0,2p)$，所以该有的三目运算总是逃不掉的。

真：

struct FastMod {
    using ull=decltype(1ull);
    using i128=__int128;
    ull p,m;
    FastMod(ull p):p(p),m((i128(1)<<64)/p) {}
    template<typename T>
    T &red(T &x) {return x>=p?x-=p:x;}
    ll operator()(__int128 x) {
        return red(x-=(x*m>>64)*p);
    }
};

另：如果没有乘法只有加法直接用 mod.red(x+=y) 更快。