大家可能听说过模数不加 const 代码变慢好多的奇怪事情：

const int mod = 998244353;
// 进行了大量 number % mod 的操作
int mod = 998244353;
// 进行了大量 number % mod 的操作，但是慢

（有符号数取模会比无符号数慢，下文将只考虑无符号数）

这是因为，编译器将模数视为常量后，会对取模操作进行优化。经实验，假设 n 是 64 位整数，n % 998244353 将会被优化为：（从汇编角度等价）

n - (__uint128_t(n) * 9920937979283557439ull >> 93) * 998244353

// 因此，我们为什么不做编译器能做的事，让编译器无事可干呢

因此，假如有一道题，模数是从输入中给定，我们是不是可以套用这个编译器的算法，将变量取模优化为常量取模呢？

查阅了一下资料，发现确实可以，而且不是很复杂。我就简化了很多细节，封装了一下，如下：（用随机数测试了一下，没出问题）

struct fastmod {
    using u64 = uint64_t;
    using u128 = __uint128_t;
    int f, l; u64 m, d;
    fastmod(u64 d): d(d) {
        l = 64 - __builtin_clzll(d - 1);
        const u128 one = 1;
        u128 M = ((one << (64 + l)) + (one << l)) / d;
        if(M < (one << 64)) f = 1, m = M;
        else f = 0, m = M - (one << 64);
    }
    friend u64 operator/(u64 n, const fastmod &m) { // get n / d
        if (m.f) return u128(n) * m.m >> 64 >> m.l;
        else {
            u64 t = u128(n) * m.m >> 64;
            return (((n - t) >> 1) + t) >> (m.l - 1);
        }
    }
    friend u64 operator%(u64 n, const fastmod &m) { // get n % d
        return n - n / m * m.d;
    }
};

// 炫酷板子++

至于原理，可以去看一下参考。

参考：SuperSodaSea：【编译笔记】变量除以常量的优化（一）——无符号除法 (opens new window)