[AGC045F] Division into Multiples

做法

首先,如果 \((A,B,C) = d > 1\),把 \(A,B,C\) 分别除去 \(d\),答案不会改变。所以我们可以假设 \((A,B,C) = 1\)

\(d_A = (A, C), d_B = (B,C)\)\(A = k_Ad_A, B = k_Bd_B\)。注意到每个盒子中,数字为 \(B\) 的球数都是 \(d_A\) 的倍数;数字为 \(A\) 的球数都是 \(d_B\) 的倍数。可以把 \(X\) 改为 \(\lfloor \frac X {d_B}\rfloor\),把 \(Y\) 改成 \(\lfloor \frac Y {d_A} \rfloor\)\(C\) 改为 \(\frac C{d_Ad_B}\)\(A\) 改为 \(k_A\)\(B\) 改为 \(k_B\)。答案不会改变。

所以我们只需要关注 \((A,C) = 1, (B,C) = 1\) 的情况。

\(0\le k < C, k \equiv B^{-1}A \pmod C\),我们用一对数 \((a,b)\) 表示一个有 \(a\) 个数为 \(A\) 的球,\(b\) 个数为 \(B\) 的球的盒子。显然我们只需要考虑下列种类的盒子:

  1. \((0, C)\)\((C,0)\)
  2. \(1 \le i < C\)\((i, C-(k i \bmod C))\)

如果盒子 \((a,b) \neq (c,d)\) 是合法的,而 \(a \le c, b \le d\),那么盒子 \((c,d)\) 是不优的,我们可以假设这样的盒子不会被用到。这样排除掉一些无用的盒子之后,我们可以得到可能有用的盒子的集合的列表 \((x_0, y_0), (x_2, y_2), \ldots, (x_n,y_n)\)\(x_i < x_{i+1}, y > y_{i+1}\),其中 \((x_0,y_0) = (0,C), (x_n,y_n) = (C,0 )\)

考虑如何从前往后求出每个 \((x_i, y_i)\),初始时我们只知道 \((x_0,y_0)\)。假设我们已知 \((x_{i-1},y_{i-1})\),要求 \((x_i,y_i)\),那么也就是要找到最小正整数的 \(x\) 使得 \(kx \bmod C < y_i\)。设 \(\Delta x_i = x_i - x_{i-1} \ (i > 0), \Delta y_i = y_i - y_{i-1}\)。这里我们找到的最小的 \(x\) 即为 \(\Delta x_i\),而 \(\Delta y_i = - (kx \bmod C)\)。如果 \(y_i \ge -\Delta y_i\),那么 \(\Delta x_{i+1} = \Delta x_i, \Delta y_{i+1} = \Delta y_i\),依次类推,可以得到以下结论:

  1. \(\Delta x_i\) 单调不减,\(-\Delta y_i\) 单调不增 (即 \(\Delta y_i\) 单调不减)。
  2. 可以把序列 \((\Delta x_1,\Delta y_1),\ldots,(\Delta x_n,\Delta y_n)\) 分为 \(\mathcal O(\log C)\) 个相同的连续段。

我们先不考虑怎么把这 \(\mathcal O(\log C)\) 个连续段求出来。

如果选了两个盒子 \((x_i,y_i)\)\((x_j,y_j)\)\(i < j\),显然调整成 \((x_{i+1},y_{i+1})\)\((x_{j-1}, y_{j-1})\) 不会变劣。通过多次这样的调整,我们可以找到一种最优方案,只有相邻两种盒子 \((x_i,y_i)\)\((x_{i+1}, y_{i+1})\) 出现过。

但是 \(n\) 可能会很大,不能遍历。我们可以对于一个 \(\Delta x_i, \Delta y_i\) 都相同的连续段 \([l,r]\),考虑只用盒子 \((x_{l-1}, y_{l-1}), \ldots, (x_r,y_r)\) 的情况。这时,\(\forall i \in [l-1,r]\)\((x_i,y_i) = (x_{l-1} + (i-l+1) \Delta x_l, y_{l-1} + (i-l+1) \Delta y_l)\)。假设我们要用 \(k\) 个盒子,设总共用了 \(N\) 个数字 \(A\)\(M\) 个数字 \(B\),那么可能的 \((N,M)\) 恰好有 \(1+k(r-l+1)\) 种:对于每个 \(0 \le i \le k(r-l+1)\)\((kx_{l-1} + i \Delta x_l, ky_{l-1} + i \Delta y_l)\) 是可能的,也就是说,能够选至少 \(k\) 个盒子的充要条件为,存在 \(0 \le i \le k(r-l+1)\) 使得 \(kx_{l-1} + i\Delta x_l \le X, ky_{l-1} + i\Delta y_l \le Y\),看成两个对 \(i\) 的范围的限制可以直接判断。直接二分 \(k\) 即可。(可能也可以讨论一下直接得到答案,不过感觉没必要) 只要对每个连续段算一次,显然就覆盖了所有只选相邻两个盒子的情况。

最后来考虑求出这些连续段的问题,用 这篇 blog 中的方法可以 \(\mathcal O(\log^2 C)\) 解决。

时间复杂度 \(\mathcal (T \log^2 C)\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int T, A, X, B, Y, C, ans;

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

void exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return;
}
// ax + by = gcd(a,b)
// bx + (a-b[a/b])y = gcd(a,b)
// ya + (x-[a/b]y)b = gcd(a,b)
int x_ = 0, y_ = 0;
exgcd(b, a%b, x_, y_);
x = y_, y = x_ - (a / b) * y_;
}

int inverse(int a, int mod) {
int x = 0, y = 0;
// ax - mod k = 1
exgcd(a, mod, x, y);
return (x % mod + mod) % mod;
}

int solve(int k, int p, int l, int r) {
if (r >= l + p) r = l + p - 1;
if (r >= p) {
int x = (l + k - 1) / k;
int res = solve(k, p, l - k * x, r - k * x);
if (res == -1) return -1;
return x + res;
}
k %= p;
if (l <= -p) {
int x = ((- p - l) / p) + 1;
l += p * x, r += p * x;
}
if (!k) {
if (l <= 0 && r >= 0)
return 0;
else
return -1;
}
int q = solve(p, k, -r, -l);
if (q == -1) return -1;
// ki >= l + qp
int ret = max(0ll, (l + 1LL * q * p + k - 1) / k);
if (k * ret > r + 1LL * q*p) {
puts("???");
}
return ret;
}

int solve(int k, int p, int l, int r, int a) {
int v = 1LL * k * a % p;
l -= v, r -= v;
return solve(k, p, l, r) + a;
}

int main() {
scanf("%d", &T);
while (T --) {
scanf("%d%d%d%d%d", &A, &X, &B, &Y, &C);
int d = gcd(gcd(A, B), C);
A /= d, B /= d, C /= d;
int dA = gcd(A, C), dB = gcd(B, C);
X /= dB, Y /= dA, C /= (dA * dB);
A /= dA, B /= dB;
ans = 0;
A %= C, B %= C;
if (!A || !B) {
if (!A && !B) {
printf("%d\n", X+Y);
} else if (!A) {
printf("%d\n", X+Y/C);
} else {
printf("%d\n", X/C+Y);
}
continue;
}
int k = 1LL * inverse(B, C) * A % C;
int cur_x = 0, cur_y = C;
while (cur_x != C) {
int nxt_x = solve(C - k, C, 0, cur_y-1, cur_x+1);
int nxt_y = 1LL * (C - k) * nxt_x % C;
int delta_x = nxt_x - cur_x, delta_y = cur_y - nxt_y;
int c = cur_y / delta_y;
nxt_x = cur_x + delta_x * c;
nxt_y = cur_y - delta_y * c;
int L = 0, R = min(cur_x ? (X / cur_x) : 0x3f3f3f3f, nxt_y ? (Y / nxt_y) : (0x3f3f3f3f)), res = 0;
while (L <= R) {
int mid = (L + R) >> 1;
ll lb = max(0LL, (1LL * mid * cur_y - Y + delta_y - 1) / delta_y), rb = min(1LL*mid*c, (X - 1LL * mid * cur_x) / delta_x);
if (lb <= rb) {
res = mid;
L = mid + 1;
} else R = mid - 1;
}
ans = max(ans, res);
cur_x = nxt_x, cur_y = nxt_y;
}
printf("%d\n", ans);
}
return 0;
}