OiClass TIGAO P3279 牛牛的方程式题解

思路

首先观察一下方程：\(ax+by+cz=d\)。观察可以得到，他有整数解当且仅当 \(\gcd(a,\, b,\, c) \equiv 0 \pmod d\)，也就是说 \(d\) 被 \(a,\, b,\, c\) 的最大公因数整除。显然这是正确的。

但是通过以上的思路，我们只能通过小样例，在面对大样例的时候这个方法仍然有些力不从心。在 \(a,\,b,\,c\) 三者之中如果出现了 \(0\)，那么显然此时公因数就会是 \(0\)，这时取余就会出事。于是我们考虑如何判断。观察大样例就会发现，这个方程有解当且仅当 \(d \neq 0\)，其余情况无解。

于是这样我们就可以不知所以然的通过这题。

听 GPT 说好像是通过拓展贝祖定理得到的，不会，可以自行 BDFS。

代码

#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

int t, a, b, c, d;

signed main() {
    freopen("func.in", "rt", stdin);
    freopen("func.out", "wt", stdout);
    cin >> t;
    while (t--) {
        cin >> a >> b >> c >> d;
        a = abs(a), b = abs(b);
        c = abs(c), d = abs(d);
        int e = __gcd(__gcd(a, b), c);
        if (e == 0) {
            if (d == 0) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        } else {
            if (d % e == 0) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }
}