3579 中国剩余定理(ACM/不互质的情况)

hdu 3579 Hello Kiki 中国剩余定理(不互质的情况) 对互质的情况，处理起来比较方便，可以直接套模板 本题给出不互质的模线性方程组，求出满足方程的最小正整数解 方案：对于不互质的模线性方程组，可以进行方程组合并，求出合并后的方程的解，这样就可以很快地推出方程的最终解。 两个方程合并的一种方法： x = c1 (mod b1） x = c2(mod b2) 此时b1,b2不必互质的。 显然可以得到x = k1 b1 + c1 x = k2 b2 + c2， 两个方程合并一下就可以得到：k1 b1 = c2 - c1 (mod b2)， 这样可以设g=gcd(b1,b2),于是就有b1/gk1-b2/gk2=(c2-c1)/g， 显然判断(c2-c1)/g是否为整数就能判断是否存在解， 这样在经过类似的变换就能得到k1 = K (mod （b2/g))， 最后得到x = Kb1 + c1 (mod (b1 * b2/g))。 对于题目所给正整数的要求，只有一种反例，就是结果输出为0的情况， 这个可以特殊考虑，只需要考虑所有数的最小公倍数即可。