bool win(int a, int b, int c, int d){
return (b + c - 1) / c + (c < a) <= (a + d - 1) / a;
}
下面开始分析每个子任务的得分方式。
Subtask 1
1. $\texttt{C}$ 只需要能击败 $\texttt{B}$，因此 $c$ 的枚举上限应为 $\max(1+b,B)$。
2. $\texttt{C}$ 必须输给 $\texttt{A}$，因此 $c$ 的枚举上限应为 $\max(a,A)-1$。
#### Subtask 2
固定 $c$ 之后，$C$ 越大 $\tt C$ 越强，$C$ 越小 $\tt C$ 越弱。
所以 $C$ 的合法取值一定在一个区间 $[l,r]$ 上，可以考虑二分 $C$。
#### Subtask 3, 5
留给一些正确性可能看起来很对的奇怪做法。~~（比如某不知名 $O(\sqrt[3]M\log M)$ 的做法）~~
#### Subtask 4
那么这部分分显然是希望我们给出一个 $O(M)$ 的线性做法。
考虑如果我们确定了 $c$，继续推一推式子（其实也就是挪一挪系数），得到：
$$b\times\left(\left\lfloor\dfrac{B}{c}\right\rfloor+[c<b]\right)~\le~C~\le~\left(\left\lfloor\dfrac{A}{c}\right\rfloor-[a<c]\right)\times a+a-1$$
据此就可以 $O(1)$ 求出 $C$ 的值。
#### Subtask 6
考虑一种更快的枚举 $c$ 的方式。
由于 $c$ 作为分母，它的取值只影响
$$\left\lceil\dfrac{A}{c}\right\rceil,\left\lceil\dfrac{B}{c}\right\rceil$$
的取值，我们可以整除分块枚举 $c$ 的取值。
一种上取整转下取整的办法：
$$\left\lceil\dfrac{p}{q}\right\rceil=\left\lfloor\dfrac{p-1}{q}\right\rfloor+1$$
另外，朴素的整除分块只枚举到
$$\min\{A,B\}$$
但是我们的 $c$ 应当一直到
$$\max\{A,B\}$$
处都可能具有贡献。
所以我们考虑根据题意分成两段枚举，第一段使用朴素的整除分块。
第二段枚举 $\min(A,B)\sim\max(A,B)$ 之间的答案贡献部分即可。
#### std
```cpp
//E1
#include<cstdio>
int init(){
char c = getchar();
int x = 0, f = 1;
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar())
x = (x << 1) + (x << 3) + (c ^ 48);
return x * f;
}
void print(int x){
if (x < 0) x = -x, putchar('-');
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
bool win(int a, int b, int c, int d){
return (b + c - 1) / c + (c < a) <= (a + d - 1) / a;
}
int mn(int a, int b){
return a < b ? a : b;
}
int mx(int a, int b){
return a > b ? a : b;
}
int main(){
int q = init();
while (q--) {
int a = init(), A = init(), b = init(), B = init();
if (win(b, B, a, A)) {
puts("-1 -1");
continue;
}
bool flag = 1;
for(int x = 1; x <= 100; ++x)
for(int y = 1; y <= 100 && flag; ++y)
if (x != a && x != b && win(b, B, x, y) && win(x, y, a, A))
flag = 0, print(x), putchar(' '), print(y), putchar('\n');
if(flag)
print(-1), putchar(' '), print(-1), putchar('\n');
}
}
//E2
#include<cstdio>
#define int long long
int init(){
char c = getchar();
int x = 0, f = 1;
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar())
x = (x << 1) + (x << 3) + (c ^ 48);
return x * f;
}
void print(int x){
if (x < 0) x = -x, putchar('-');
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
bool win(int a, int b, int c, int d){
return (b + c - 1) / c + (c < a) <= (a + d - 1) / a;
}
int mn(int a, int b){
return a < b ? a : b;
}
int mx(int a, int b){
return a > b ? a : b;
}
signed main(){
int q = init();
while (q--) {
int a = init(), A = init(), b = init(), B = init();
int MAX = mn(mx(1 + b, B), mx(a, A) - 1);
int M = mx(mx(a, A), mx(b, B));
if (!win(a, A, b, B) || (B > A && b > a)) {
puts("-1 -1");
continue;
}
bool flag=1;
for (int c = 1; c <= MAX; ++c) {
if (c == a || c == b)
continue;
int l = 1, r = (M - 1) * (M - 1), ans = -1;
if (c > a) r = A - 1;
if (c < b) l = B + 1;
while (l <= r) {
int mid = l + r >> 1;
if (!win(c, mid, a, A))
r = mid - 1;
else if (!win(b, B, c, mid))
l = mid + 1;
else {
ans = mid;
break;
}
}
if (ans != -1) {
print(c), putchar(' '), print(ans), putchar('\n');
flag = 0;
break;
}
}
if (flag)
puts("-1 -1");
}
}
//E3
#include<cstdio>
#define int long long
int init(){
char c = getchar();
int x = 0, f = 1;
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar())
x = (x << 1) + (x << 3) + (c ^ 48);
return x * f;
}
void print(int x){
if (x < 0) x = -x, putchar('-');
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
bool win(int a, int b, int c, int d){
return (b + c - 1) / c + (c < a) <= (a + d - 1) / a;
}
int a, A, b, B;
int ok(int c){
if (c == a || c == b)
return 0;
int l = b * (B / c + (c < b)),
r = (A / c - (a < c)) * a + a - 1;
if (l > r)
return 0;
return l + 1;
}
int mn(int a, int b){
return a < b ? a : b;
}
int mx(int a, int b){
return a > b ? a : b;
}
signed main(){
int t = init();
for (int i = 1; i <= t; ++i) {
a = init(), A = init(), b = init(), B = init();
if (!win(a, A, b, B) || (B > A && b > a)) {
puts("-1 -1");
continue;
}
--A, --B;
int c = 0, C;
if (!ok(a + 1) && !ok(b + 1)) {
for (int i = 1; i <= mx(A, B); ++i)
if (ok(i)) {
c = i, C = ok(i);
break;
}
}
else {
if (ok(a + 1))
c = a + 1, C = ok(a + 1);
if (ok(b + 1))
c = b + 1, C = ok(b + 1);
}
if (c)
print(c), putchar(' '), print(C), putchar('\n');
else
puts("-1 -1");
}
}
//E4
#include<cstdio>
#define int long long
int init(){
char c = getchar();
int x = 0, f = 1;
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar())
x = (x << 1) + (x << 3) + (c ^ 48);
return x * f;
}
void print(int x){
if (x < 0) x = -x, putchar('-');
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
bool win(int a, int b, int c, int d){
return (b + c - 1) / c + (c < a) <= (a + d - 1) / a;
}
int a, A, b, B;
int ok(int c){
if (c == a || c == b)
return 0;
int l = b * (B / c + (c < b)),
r = (A / c - (a < c)) * a + a - 1;
if (l > r)
return 0;
return l + 1;
}
int mn(int a, int b){
return a < b ? a : b;
}
int mx(int a, int b){
return a > b ? a : b;
}
signed main(){
int t = init();
for (int i = 1; i <= t; ++i) {
a = init(), A = init(), b = init(), B = init();
if (!win(a, A, b, B) || (B > A && b > a)) {
puts("-1 -1");
continue;
}
--A, --B;
int c = 0, C;
if (!ok(a + 1) && !ok(b + 1)) {
for (int i = 1; i <= A && i <= B; i = mn(A / (A / i), B / (B / i)) + 1)
if (ok(i)) {
c = i, C = ok(i);
break;
}
for (int i = mn(A, B) + 1; i <= mx(A, B); i = mx(A, B) / (mx(A, B) / i) + 1)
if (ok(i)) {
c = i, C = ok(i);
break;
}
}
else {
if (ok(a + 1))
c = a + 1, C = ok(a + 1);
if (ok(b + 1))
c = b + 1, C = ok(b + 1);
}
if (c)
print(c), putchar(' '), print(C), putchar('\n');
else
puts("-1 -1");
}
}
```