poj 2891Strange Way to Express Integers 中国剩余定理（不互质) 数据没读完就结束了程序居然是runtime error。

### POJ2891 Strange Way to Express Integers 的算法解析 此问题的核心在于通过扩展中国剩余定理来解决一组模线性同余方程组。当模数不一定两两互质时，可以通过逐步合并的方式解决问题。 #### 扩展中国剩余定理的应用 对于两个同余方程 \( N \equiv r_1 \ (\text{mod} \ m_1) \) 和 \( N \equiv r_2 \ (\text{mod} \ m_2) \)，我们需要找到满足这两个条件的最小非负整数解。设 \( d = \gcd(m_1, m_2) \)，则存在整数解的前提是 \( (r_2 - r_1) \% d == 0 \)[^4]。如果该条件成立，则可通过扩展欧几里得算法求出特解并进一步计算通解。 具体步骤如下： 1. **初始化参数** 设初始状态为 \( M = m_1 \) 和 \( R = r_1 \)。 2. **逐对处理每一对模数和余数** 对于当前的状态 \( M \) 和 \( R \)，以及新的模数 \( m_i \) 和余数 \( r_i \)，我们尝试将其合并成一个新的同余关系： \[ xM + ym_i = r_i - R \] 如果 \( (r_i - R) \% gcd(M, m_i) != 0 \)，说明无解；否则继续下一步。 3. **利用扩展欧几里得算法求解系数** 使用扩展欧几里得算法求解上述不定方程的一组特解 \( x_0 \) 和 \( y_0 \)。然后调整这些系数使得最终的结果落在有效范围内。 4. **更新全局变量** 更新后的模数为 \( lcm(M, m_i) \)，而对应的余数则是新算出来的值加上原来的偏移量。 5. **重复直到完成所有输入数据** 最后得到的 \( R \) 即为目标答案。 以下是基于 Python 实现的一个版本： ```python from math import gcd def ex_gcd(a, b): """扩展欧几里得算法""" if b == 0: return a, 1, 0 g, x, y = ex_gcd(b, a % b) return g, y, x - (a // b) * y def solve(): k = int(input()) mods = [] rems = [] for _ in range(k): mi, ri = map(int, input().split()) mods.append(mi) rems.append(ri) M = mods[0] R = rems[0] for i in range(1, len(mods)): Mi = mods[i] Ri = rems[i] g, p, q = ex_gcd(M, Mi) if (Ri - R) % g != 0: print(-1) # No solution exists. return tmp = ((Ri - R) // g) * p % (Mi // g) R += M * tmp M *= Mi // g while R < 0: R += M print(R % M) if __name__ == "__main__": T = int(input()) # Number of test cases results = [] for t in range(T): solve() ``` 以上程序实现了扩展中国剩余定理的方法，并能够正确处理多组测试样例的情况。 --- ####