Miller-Rabin判定中pow_mod必须用快速幂配合手写mul_mod防溢出，因a*b可能超2^64；mul_mod需分治实现、特判0/1；pow_mod指数须为uint64_t；底数a选取需严谨。
Miller-Rabin 判定中 pow_mod 必须用快速幂 + 模乘防溢出
直接调 std::pow 或 a * b % mod 会爆 long long —— 即便 n 是 uint64_t 量级，中间乘积也可能超 2^64。比如判 n = 10^18 时，a 和 b 都可能接近 n，a * b 轻松突破 1e36。
必须手写模乘：用类似快速幂的分治思想做 mul_mod(a, b, mod)，每次加法后取模，避免任何一步超过 mod 的两倍（对 uint64_t 安全）。常见错误是漏掉这层封装，导致判定结果随机翻车。
- 别用
__int128当通用解法——它在 Windows/MSVC 和部分在线评测机上不可用 -
mul_mod输入若含 0 或 1，要单独返回，避免循环开销 - 快速幂
pow_mod的指数参数必须是uint64_t，不能是int（强伪素数测试里指数常达n-1）
选底数 a 不是随便挑几个小质数就完事
对 uint64_t 范围内的数（n ），已知确定性集合只有 12 个：<code>{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}。但实际只需前 7 个就能覆盖全部——{2, 325, 9375, 28178, 450775, 9780504, 1795265022}（Jacobian 等人验证过）。硬写死小质数如 {2, 3, 5, 7} 只能保证 n 正确，大于这个值就会漏判合数。
- 如果
n ，用 <code>{2, 7, 61}就够了，快且确定 - 若
n是用户输入的字符串（比如 100 位十进制数），得先转成__uint128_t或用大数库；此时 Miller-Rabin 仅作概率性预筛，不能当最终结论 - 底数
a必须满足1 ，等于 <code>n-1会导致a ≡ -1 (mod n)，干扰二次探测判断
n 是合数但通过所有轮次，就是强伪素数
Miller-Rabin 本质是检验：对给定 a，是否满足 a^(n−1) ≡ 1 (mod n)，且在分解 n−1 = d × 2^s 后，序列 a^d, a^(2d), ..., a^(2^(s−1)d) 中要么首个为 1，要么某个为 −1 (mod n)。不满足即合数；全满足只是“疑似素数”。
立即学习“C++免费学习笔记（深入）”；
- 单轮误判率 ≤ 1/4，跑
k轮后 ≤4^(−k)；但对特定n，存在某些a总让它蒙混过关——这就是强伪素数（如n = 2047对a = 2就是） - 代码里别写
if (is_composite) return false;就完事——得确保每轮都完整走完二次探测链，不能提前 break 出错分支 - 注意
n = 2和n = 3是素数，n % 2 == 0且n != 2直接返回 false，否则后续n−1为奇数，无法分解出2^s
实际调用时必须先做小因子筛
Miller-Rabin 是重操作，对明显合数（如末位是偶数、被 3 或 5 整除）应提前拦截。否则像 n = 1000000000000000000 这种数，连 pow_mod 都不用跑就知道是合数。
- 建议预筛前 100 个质数（最大到 541），用试除法；对
uint64_t数，最多试到sqrt(n) ≈ 1e9不现实，但小因子占比极高 - 特别检查
n == 1（不是素数）、n == 0（非法输入）、n （只认 2 和 3） - 如果项目允许依赖，
boost::multiprecision::cpp_int内置的is_probably_prime底层也是 Miller-Rabin，但默认只跑 25 轮——你得看文档确认它用的底数集是否覆盖你的n范围
强伪素数判定的难点不在算法逻辑，而在数值边界和底数选择的精确性。写一遍容易，让结果在 2^64 内全对，得抠每个常量和溢出点。
