[POJ2891] Strange Way to Express Integers

题目

题目链接 POJ 2891.给定模线性方程组求最小整数解。
 

思路

因为不保证互质,所以只能采用两两合并的方式。
对于方程组  \left\{ \begin{aligned} X = a_1 x + r_1 \\ X = a_2 y + r_2 \end{aligned} \right. . 即有 a_1 x + r_1 = a_2 y + r_2, 即有 a_1 x - a_2 y = r_2 - r_1 用扩展欧几里得可以求出最小正整数解 x, 即最小正整数解 X = a_1 x + r_1. 我们便可以构造一个新的方程。X = A x + R, 其中 R = a_1 x + r_1 \ \ A = lcm(a_1, a_2).
不断的两两合并便可以求得最终解。
 

代码

 

完结

发表评论

电子邮件地址不会被公开。 必填项已用*标注