题目链接：Codeforces 1143D

在 Byteland 有 $n\times k$ 个城市，所有城市围成了一个环，相邻城市之间的距离恰好为 $1\text{km}$。

Sergey 喜欢汉堡。幸运的是，这 $n\times k$ 个城市中一共有 $n$ 家快餐店，他们位于第 $1, k + 1, 2k + 1, \cdots, (n - 1)k + 1$ 个城市。显然相邻快餐店的距离为 $k\text{km}$。

Sergey 从第 $s$ 个城市开始旅行，他每经过 $l\text{km}(l > 0)$ 停下来休息一次，直到重新回到城市 $s$。虽然 Sergey 忘记了 $s$ 和 $l$ 的值，但是他记得城市 $s$ 距离最近的快餐店 $a\text{km}$，他第一次停下休息的城市距离最近的快餐店 $b\text{km}$。他旅行的方向是不变的，但是他计算距离的方向的双向的。

现在 Sergey 只关心 $2$ 个数字 $x, y$，分别表示他重新回到 $s$ 需要的最少和最多休息次数。

数据范围：$1\le n, k\le 10 ^ 5$，$0\le a, b\le \frac{k}{2}$。

Solution

首先注意到，对于确定的 $l$，需要休息 $\frac{nk}{\gcd(nk, l)}$ 次。那么我们将 $(a, b)$ 分为 $(a, b), (-a, b), (a, -b), (-a, -b)$ 四类进行计算。每次可以 $\mathcal O(n)$ 枚举距离 $l$ 然后更新答案。

时间复杂度：$\mathcal O(n\log n)$。

Code

#include <cstdio>
#include <algorithm>

typedef long long LL;

const LL INF = 0x7f7f7f7f7f7f7f7f;

LL n, k, a, b, mn = INF, mx = -INF;

void calc(LL a, LL b) {
    for (; b <= n * k; b += k) {
        LL d = std::abs(a - b);
        if (d == 0) continue;
        LL cnt = n * k / std::__gcd(n * k, d);
        mn = std::min(mn, cnt);
        mx = std::max(mx, cnt);
    }
}
int main() {
    scanf("%lld%lld%lld%lld", &n, &k, &a, &b);
    if (a == b) mn = 1;
    calc(a, b);
    calc(k - a, b);
    calc(a, k - b);
    calc(k - a , k - b);
    printf("%lld %lld\n", mn, mx);
    return 0;
}