核心概述
模运算（Modular Arithmetic）：在给定正模 m 下进行加减乘规约、规范化与常见组合操作的通用模板；处理负数规约、溢出安全乘法、幂与逆等常见细节。
原文引述
Description: Utilities for modular arithmetic: normalize to [0,m), constant-time add/sub with wrap-around, safe multiply (u128/Barrett/Montgomery), and ModInt wrapper integrating pow/inv. Time: O(1) per op (amortized) Status: tested
-
函数/接口（据常见实现）
- normMod(a, m) → 将任意整数 a 规范到 [0, m)。
- addMod(a, b, m) / subMod(a, b, m) → 返回 (a±b) mod m，常用“若超界加/减 m”的分支避免取模。
- mulMod(a, b, m) → (a·b) mod m（64 位用 __int128 或参见 090-数论-长整型模乘）。
- powmod(a, e, m) → a^e mod m（见 091-数论-模幂）。
- inv(a, m) → a^{-1} mod m（若 gcd(a,m)=1，见 088-数论-模逆）。
- 结构体 ModInt
或 runtime Mod： - 字段 v ∈ [0, MOD)；重载 +,-,*,/,+=, …；/ 调用 inv。
- 支持快速幂、读写与与整型互转；可提供 getMod/setMod（运行时模）。
-
规范化与边界
- 负数规约：((a % m) + m) % m 保证落在 [0, m)。
- m==1 的约定：所有结果为 0（避免除以 0 的操作）。
- 加减包裹：
- add: x += y; if (x >= m) x -= m
- sub: x -= y; if (x < 0) x += m
- 乘法溢出：优先 __int128；若不可用，采用 Barrett/Montgomery（见 090-数论-长整型模乘）。
-
组合套路
- 幂与逆：powmod 二进制快速幂；素数模逆用 a^{p-2}；一般模逆用扩展欧几里得（088-数论-模逆、091-数论-模幂、083-数论-欧几里得算法）。
- CRT 合并：多模约束合并为单模（081-数论-中国剩余定理）。
- 模平方根：素数模下用 Tonelli–Shanks（092-数论-模平方根）。
- 模和/地板和：配合 floor-sum 模板计算批量取模和（093-数论-模求和）。
-
实现要点
- 统一类型与取模次数：尽量减少重复 % 操作，先规范再复用。
- 对性能敏感路径，使用分支而非 % 降常数；乘法采用安全乘。
- ModInt 需注意：
- 常量 MOD 为编译期常量时便于优化；运行时模需小心全局状态。
- 除法仅在可逆时定义；调试模式可断言 gcd(v, MOD)==1。
- 与内置整型的隐式转换要谨慎，避免精度与符号陷阱。
-
输出语义
- 所有结果规范到 [0, m)；ModInt 封装保证不变式成立。
-
复杂度
- 基本加减 O(1)；乘法 O(1)（取决于后端）；幂/逆参见对应模板。
-
使用与注意
- 溢出与 UB：所有中间运算用无符号与 128 位/降余法实现。
- 选择后端：
- 少量运算：__int128 最简洁；
- 批量固定奇模：Montgomery 较优；
- 跨模或平台限制：Barrett 降余更通用。
- 与随机大数判素/分解等算法同用时，务必采用安全模乘。