统计线段上格点的数量

题意解析

令 $X = \vert x_A - x_B \vert, Y = \vert y_A - y_B \vert$，那么我们可以将题目转化为：求最多可以将 $X$ 和 $Y$ 均分为多少段，使得每段的长度均为整数。

令均分的段数为 $k$，那么我们需要求的结果就是找到一个可以整除 $X$ 和 $Y$ 的最大的 $k$。

也就是 $X$ 和 $Y$ 的最大公约数，即 $\gcd(X, Y)$。

答案即为 $\gcd(X, Y) + 1$。

AC代码

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int xa, ya, xb, yb;
        cin >> xa >> ya >> xb >> yb;
        int x = abs(xa - xb), y = abs(ya - yb);
        cout << gcd(x, y) + 1 << '\n';
    }
    return 0;
}

复杂度分析

对于每个 $Testcase$ 求取 $X$ 和 $Y$ 的最大公约数时间复杂度为 $\mathrm{O}(\log{\max{(X, Y)}})$。