兔八哥与猎人(Bugs Bunny and the Hunter) 题解

思路分析

设水平距离 $dx = |a_x - b_x|$，垂直距离 $dy = |a_y - b_y|$。连接整点 $(a_x, a_y)$ 与 $(b_x, b_y)$ 的线段上（不含两端点）包含的整点果树棵数恰好为 $\gcd(dx, dy) - 1$。因此当 $\gcd(dx, dy) == 1$ 时中间没有果树遮挡，兔八哥不安全，输出 no；当 $\gcd(dx, dy) > 1$ 时中间有果树遮挡，输出 yes（注意同行或同列时其中一个差值为 $0$，$\gcd(0, k) = k$ 同样适用）。单次询问 $O(\log V)$。

参考代码

#include <cstdlib>
#include <iostream>
using namespace std;

long long myGcd(long long a, long long b)
{
    while (b != 0)
    {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    while (n--)
    {
        long long ax, ay, bx, by;
        cin >> ax >> ay >> bx >> by;
        long long dx = (ax > bx) ? (ax - bx) : (bx - ax);
        long long dy = (ay > by) ? (ay - by) : (by - ay);
        if (myGcd(dx, dy) == 1) cout << "no\n";
        else cout << "yes\n";
    }
    return 0;
}