c++ - 求解联立模方程的代码？

Question

这里的符号 = 用于表示“一致于”

如果

(1) n = a mod j
(2) n = b mod k

然后

(3) n = c mod l

基本上，给定前两个方程，找到第三个。出于我的目的，我事先知道存在解决方案。

我想要一些 C 或 C++ 中的代码来为我做这件事，或者一个库的链接或我可以在 C/C++ 项目中使用的东西。谢谢。

Answer 1

如果给定 a、b、j 和 k，l = jk，并且 gcd(j,k) = 1，则可以使用中国剩余定理找到 c 。（如果 j 和 k 有一个非平凡的 GCD，则解 c 可能存在也可能不存在。）

Answer 2

一个表示无限算术序列的库在这里会很有用，但我个人不知道。无论如何，这是一个蛮力解决方案，它基本上为n每个给定的模方程生成可能性并找到交集。n它通过“跨越式”（伪代码）找到 的最小值：

value_left := a
value_right := b

while value_left != value_right:
    if value_left < value_right:
        value_left := value_left + j
    else:
        value_right := value_right + k
    end if
end while loop

return value_left % l // as in "leggo-mah-eggo!"

如果您想要实际的 C 代码，请告诉我，尽管翻译应该相当简单。