面试题库 › 嵌入式 › 已知n对多个数取模的结果求n(中国剩余定理)

已知n对多个数取模的结果求n(中国剩余定理)

难度 ★★★在 1 场真实面经中被问到 方向:嵌入式考点:数学与智力题

哪些公司问过

字节跳动1

常见岗位:嵌入式软件

答案要点

  1. 本质是同余方程组,模数两两互质时用中国剩余定理直接构造
  2. 每项 Mi=M/mi,用扩展欧几里得求 Mi 模 mi 的逆元
  3. 模数不互质时两两合并,先检查 (a2−a1) 能否被 gcd 整除
  4. 合并后的模数是 lcm,通解为最小解加上 lcm 的整数倍
  5. 数据小时也可以用步长递增的枚举法逐个满足条件

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题