非常妙的题。
先直观感受一下,显然当 \(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\),所以:
发现 \(qB - V + M + 1 - A \le qB + B - 1 - V\),所以我们可以直接 \(r - l + 1\) 求出 \(n\) 的数量。考虑二分最小的 \(q'\) 使得存在一个 \(q \in [0, q']\) 使得上面至少能解出一组解,那么需要满足:
到这里就是一个比较标准的类欧形式了。于是我们可以 \(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;
}
- AtCoder Regular Contest 127 177atcoder regular contest 127 atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest 167 atcoder regular contest sliding atcoder regular contest degree atcoder regular contest 164 atcoder regular contest builder subsegments atcoder regular contest