核心概述
快速取模通过位运算、查表或编译器友好替代手段规避除法开销，以常数时间完成高频模运算。
原文引述
Description: Fast modulo operations using bit tricks, lookup tables, or compiler-friendly alternatives. Avoids expensive division/modulo for small or power‑of‑two moduli.（摘自本节点现有英文注释） Time: O(1) per operation (no division)（摘自本节点现有英文注释） Status: tested（摘自本节点现有英文注释）
展开阐述
-
定义与背景
- 面向频繁的取模场景（尤其模 2^k 或小模数），通过按位与、查表、或将常数除法由编译器优化为乘法+移位，显著降低常数开销。
-
接口/数据结构与语义（依仓库惯例）
- 模 2^k：
x & ((1<<k)-1)，等价于x % (1<<k)但常数更小。 - 模 2^k−1（Mersenne）：通过重复归约（如
(x & M) + (x >> k)）实现快速收敛。 - 模小素数（< 2^16）：预计算逆元
inv[b] = b^{-1} mod p，用乘法代替除法。 - 通用 fallback：若 m 非 2 的幂，则回退使用
%。
- 模 2^k：
inline int mod2k(int x, int k) { return x & ((1<<k) - 1); }
static const int MOD = 9973;
static int inv[MOD]; // precomputed
inline int modMul(int a, int b) { return (a * b) % MOD; }
inline int modDiv(int a, int b) { return a * inv[b] % MOD; }
inline int fastMod(int x, int m) {
if (m & (m-1)) return x % m; // not power of two
return x & (m-1);
}-
核心流程与关键要点
- 选择策略：优先利用位运算（2 的幂）、其次查表（小素数），其余情况交由编译器或显式回退。
- 负数规范化：结果需非负时，可用
(x % m + m) % m。 - 64 位：位操作时使用
1ULL与按位与，避免溢出与未定义行为。 - 与容器/哈希的结合：容量常取 2 的幂以便用位与代替
%。
-
复杂度与边界条件
- 单次 O(1)；空间换时间时（查表）需权衡内存占用与命中收益。
- 当 m 非常量时，编译器对
%的优化有限，手动分支可更稳。
-
常见变体/扩展
- 针对固定小模数族的多模取模，可共用一张逆元表。
- 与状态压缩/滚动数组类 DP 场景结合，减少取模热路径开销。