核心概述
模幂（Modular Exponentiation, powmod）：用于在给定模 m 下以二进制快速幂计算 a^e mod m，时间复杂度 O(log e)，在 64 位大模时需配合安全模乘（如 __int128、Barrett 或 Montgomery）防止溢出。
原文引述
Description: Fast modular exponentiation using binary exponentiation. Supports safe 64-bit modular multiply (u128/Barrett/Montgomery). Time: O(log e) multiplications
展开阐述
-
函数/接口（据实现）
- ll powmod(ll a, unsigned long long e, ll m)：返回 a^e mod m（m>0）。
- u64 powmod_u64(u64 a, u64 e, u64 m, Mul mul=mul128)：mul 为 (x,y)↦(x·y mod m) 的安全模乘（见 090-数论-长整型模乘）。
- 特例：当 m 为奇素数且需大量乘法，可用 Montgomery 版本 powMont。
-
核心算法（二进制快速幂）
- 规范化：a = (a % m + m) % m；若 m==1 返回 0；res=1 % m。
- 迭代：
- while (e > 0):
- if (e & 1) res = mul(res, a)。
- a = mul(a, a)。
- e >>= 1。
- while (e > 0):
- 返回 res。对于 e0，按约定返回 1 mod m（即使 a0，常取 1）。
-
安全与实现要点
- 溢出防护：乘法用 __int128 或 Barrett/Montgomery（见 090-数论-长整型模乘）。
- 负底数：先规约至 [0,m)。
- 指数类型：用无符号 64 位可涵盖常见场景；大指数可用大整数按位迭代。
- 定模优化：固定奇模、多次乘幂时，Montgomery 常数更小（需 toMont/fromMont）。
-
典型用途
- 087-数论-米勒拉宾 中的幂检验。
- 088-数论-模逆 在素数模下用 a^{p−2} 计算逆元。
- 幂等构造、循环节检测、快速多项式评估等。
-
输出语义
- 返回 a^e 在模 m 下的值，位于 [0,m)。
-
复杂度
- 乘法次数约为 ⌊log2(e)⌋·2 次（含平方与若干乘）；总体 O(log e)。
-
使用与注意
- m1 直接返回 0；e0 返回 1 % m。
- 若 m 很大且平台无 128 位，优先 Barrett；大量乘法用 Montgomery。
- 对于随机大数测试/分解，务必搭配安全模乘防止 UB。