已知n对多个数取模的结果求n(中国剩余定理)
哪些公司问过
答案要点
- 本质是同余方程组,模数两两互质时用中国剩余定理直接构造
- 每项 Mi=M/mi,用扩展欧几里得求 Mi 模 mi 的逆元
- 模数不互质时两两合并,先检查 (a2−a1) 能否被 gcd 整除
- 合并后的模数是 lcm,通解为最小解加上 lcm 的整数倍
- 数据小时也可以用步长递增的枚举法逐个满足条件
易错点
- 模数不互质时直接套 CRT 公式,得到错误结果
- 合并时没检查相容性,无解的情况误输出答案
- 中间乘积溢出,没有用快速乘或更大整型
面试官常见追问
- 扩展欧几里得的作用是什么?
- 不用 CRT 有没有简单做法?
- 乘积很大时要注意什么?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。