自动搬运

查看原文

来自洛谷，原作者为

	WorldMachine 请引领我至夜晚熠熠闪烁的群星之下

搬运于2025-08-24 21:35:56，当前版本为作者最后更新于2024-12-18 17:06:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

同余方程组

$$\left\{ \begin{aligned} x\equiv b_1\pmod{a_1}\\ x\equiv b_2\pmod{a_2} \end{aligned} \right. $$

有解，当且仅当 $\gcd(a_1,a_2)|(b_2-b_1)$。

证明：联立两式得 $x=b_1+k_1a_1=b_2+k_2a_2$，即 $k_1a_1-k_2a_2=b_2-b_1$，由裴蜀定理得其有解条件为 $\gcd(a_1,a_2)|(b_2-b_1)$。

本题直接暴力 check 即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int T, n, a[N], b[N];
bool flg;
void solve() {
	flg = 1;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> b[i] >> a[i], a[i] = b[i] - a[i];
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if ((a[j] - a[i]) % __gcd(b[i], b[j])) { flg = 0; break; }
		}
		if (!flg) break;
	}
	cout << (flg ? "possible" : "impossible") << '\n';
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) solve();
}