题解：P2284 [HNOI2003] 密室之门

WorldMachine · 2024-12-18 17:06:33 · 题解

同余方程组

有解，当且仅当 \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();
}