CF1142A The Beatles

最近在 Byteland 发现了一个金色甲虫爱好者圆环。这是一个经过 $n \cdot k$ 个城市的环形路线。城市编号为 $1$ 到 $n \cdot k$，相邻城市之间的距离恰好为 $1$ 千米。 Sergey 不喜欢甲虫，他喜欢汉堡。幸运的是，圆环上有 $n$ 家快餐店，分别位于第 $1$ 个、第 $(k+1)$ 个、第 $(2k+1)$ 个，依此类推，第 $((n-1)k+1)$ 个城市。也就是说，相邻两家快餐店之间的距离为 $k$ 千米。 Sergey 从某个城市 $s$ 出发，沿着圆环每隔 $l$ 千米（$l > 0$）停一次，直到再次停在 $s$。Sergey 忘记了 $s$ 和 $l$ 的具体数值，但他记得从起始城市 $s$ 到最近的快餐店的距离是 $a$ 千米，从他第一次停下的城市到最近快餐店的距离是 $b$ 千米。Sergey 总是沿着同一方向行进，但在计算到快餐店的距离时，会考虑两个方向。 现在 Sergey 想知道两个整数。第一个整数 $x$ 表示 Sergey 在回到 $s$ 之前（不包括第一次）最少可能停下的次数。第二个整数 $y$ 表示 Sergey 在回到 $s$ 之前（不包括第一次）最多可能停下的次数。

第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 100\,000$），分别表示圆环上的快餐店数量和相邻快餐店之间的距离。 第二行包含两个整数 $a$ 和 $b$（$0 \le a, b \le \frac{k}{2}$），分别表示起始城市和第一次停下的城市到最近快餐店的距离。

输出两个整数 $x$ 和 $y$。

在第一个样例中，快餐店位于第 $1$ 和第 $4$ 个城市，起始城市 $s$ 可能是第 $2$、$3$、$5$ 或 $6$ 个城市。Sergey 第一次停下的城市也可能是第 $2$、$3$、$5$、$6$ 个城市。遍历所有可能的组合。如果 $s$ 和第一次停下的城市都是第 $2$ 个（例如 $l=6$），那么 Sergey 在第一次停下后就已经回到了 $s$，所以 $x=1$。在其他组合中，Sergey 需要 $1, 2, 3$ 或 $6$ 次停下才能回到 $s$，因此 $y=6$。 在第二个样例中，Sergey 起始和第一次停下都在有快餐店的城市，因此 $l$ 可能为 $2$、$4$ 或 $6$。所以 $x=1$，$y=3$。 在第三个样例中，只有一家快餐店，$s$ 和第一次停下的城市可能是 $(6, 8)$ 和 $(6, 4)$。对于第一种情况，$l=2$，第二种情况 $l=8$。两种情况下 Sergey 都需要 $x=y=5$ 次停下才能回到 $s$。 由 ChatGPT 4.1 翻译