非常妙的题。
先直观感受一下，显然当 \(M\) 大到一定程度后，\([0, M]\) 的所有数都能被取到。考虑 \(V \gets V + Ax + By\)，其中 \(V + Ax + By \in [0, M]\)。如果 \(x, y\) 都是正数显然可以取到。如果一正一负，比如 \(x > 0, y \le 0\)，那可以先把 \(V\) 一直减 \(B\) 直到减够 \(|y|\) 次，此时 \(V < B\)，然后再加 \(A\)，再重复操作。因为 \(A + B \le M + 1\)，所以当 \(V < B\) 时 \(V + A\) 一定 \(\le M\)。所以此时可以取到任意 \(V + Ax + By \in [0, M]\) 的值（因为 \(\gcd(A, B) = 1\)）。
当 \(A + B \ge M + 2\) 时，不妨先 \(V \gets V \bmod A\)。考虑我们先 \(+ A\)，那么此时若不能走到重复的数，只能选择 \(+ A\) 或者 \(- B\)。并且因为 \(A + B > M\)，所以至多有一种选择。因此我们如果确定了一开始的操作，之后的操作序列是确定的。
可以证明若一开始的操作确定，那后面不会走到相同的数。设 \(Ax = By\)，那么 \(x, y\) 最小正整数解是 \(x = B, y = A\)（因为 \(\gcd(A, B) = 1\)）。因为 \(A + B \ge M + 2\)，所以在走到之前一定已经形成了环。
还可以证明一开始的操作不同，后面也不会走到相同的数。因为若走到相同的数，另一种走法只能倒着回到起点，矛盾。
所以我们两种走法就是独立的了。现在先讨论一开始选择 \(+ A\)。
考虑采用一开始的走法。先不断 \(V \gets V + A\)，直到某一刻 \(V \ge B\)，令 \(V \gets V - B\)。设走了 \(n\) 次 \(+ A\)，那么走了 \(\left\lfloor\frac{V + nA}{B}\right\rfloor\) 次 \(- B\)。并且因为之后就走不动了，所以 \((V + nA) \bmod B + A \ge M + 1\)。
但是到这一步我们仍不能直接确定最小的 \(n\) 使得它满足上面的条件。考虑设 \(q = \left\lfloor\frac{V + nA}{B}\right\rfloor\)，那么 \(qB \le V + nA < (q + 1)B\)，并且 \(V + nA - qB \ge M + 1 - A\)，所以：
\[\left\lceil\frac{qB - V + M + 1 - A}{A}\right\rceil \le n \le \left\lfloor\frac{qB + B - 1 - V}{A}\right\rfloor \]发现 \(qB - V + M + 1 - A \le qB + B - 1 - V\)，所以我们可以直接 \(r - l + 1\) 求出 \(n\) 的数量。考虑二分最小的 \(q'\) 使得存在一个 \(q \in [0, q']\) 使得上面至少能解出一组解，那么需要满足：
\[\sum\limits_{i = 0}^{q'} \left\lfloor\frac{qB + B - 1 - V}{A}\right\rfloor - \sum\limits_{i = 0}^{q'} \left\lfloor\frac{qB - V + M + 1 - A}{A}\right\rfloor \]\[= \sum\limits_{i = 0}^{q'} \left\lfloor\frac{qB + B - 1 - V}{A}\right\rfloor - \sum\limits_{i = 0}^{q'} (\left\lfloor\frac{qB - V + M + 1}{A}\right\rfloor - 1) \]到这里就是一个比较标准的类欧形式了。于是我们可以 \(O(\log M)\) check。总复杂度就是 \(O(T \log^2 M)\) 的。
code
// Problem: F - ±AB
// Contest: AtCoder - AtCoder Regular Contest 127
// URL: https://atcoder.jp/contests/arc127/tasks/arc127_f
// Memory Limit: 1024 MB
// Time Limit: 8000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
ll dfs(ll a, ll b, ll c, ll n) {
if (!a || !n) {
return (n + 1) * (b / c);
}
if (n < 0) {
return 0;
}
if (a >= c || b >= c) {
return dfs(a % c, b % c, c, n) + (a / c) * (n * (n + 1) / 2) + (b / c) * (n + 1);
}
ll m = (a * n + b) / c;
return m * n - dfs(c, c - b - 1, a, m - 1);
}
inline ll calc(ll p, ll q, ll r, ll n) {
return dfs(p, r, q, n);
}
void solve() {
ll A, B, n, m;
scanf("%lld%lld%lld%lld", &A, &B, &m, &n);
if (A + B - 1 <= n) {
printf("%lld\n", n + 1);
return;
}
ll V = m % A;
ll ans = 1, l = 0, r = n + 5, pos = -1;
while (l <= r) {
ll mid = (l + r) >> 1;
if (calc(B, A, B - 1 - V, mid) - (calc(B, A, n - V, mid) - mid - 1) > 0) {
pos = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
ll t = (pos * B - V + n) / A;
ans += t + (V + t * A) / B;
swap(A, B);
l = 0;
r = n + 5;
pos = -1;
while (l <= r) {
ll mid = (l + r) >> 1;
if (calc(B, A, B - 1 - V, mid) - (calc(B, A, n - V, mid) - mid - 1) > 0) {
pos = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
t = (pos * B - V + n) / A;
ans += t + (V + t * A) / B;
printf("%lld\n", ans);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}