当时在 GDCPC 现场是这题首杀。20min 就会了，但是 2h 才有电脑写（
观察到至多 \(50\) 组数据满足 \(\max(x, y) > 10^6\)，考虑一些根号做法。
当 \(f(x, a)\) 的长度 \(\ge 3\) 时，\(a \le \sqrt{x}\)，因此可以暴力做，先找出所有 \(f(x, a)\)，再找出所有 \(f(y, b)\)，套个 map 找相等。
当 \(f(x, a)\) 的长度 \(\le 2\) 时，我们有：
- \(\left\lfloor\frac{x}{a}\right\rfloor = \left\lfloor\frac{y}{b}\right\rfloor\)
- \(x \bmod a = y \bmod b\)
后者等价于 \(x - a \left\lfloor\frac{x}{a}\right\rfloor = y - b \left\lfloor\frac{y}{b}\right\rfloor\)。设 \(t = \left\lfloor\frac{x}{a}\right\rfloor = \left\lfloor\frac{y}{b}\right\rfloor\)，那么有 \(x - at = y - bt\)，化简得 \(b - a = \frac{y - x}{t}\)。
整除分块套个 map 找到所有 \(\left\lfloor\frac{x}{a}\right\rfloor\) 和 \(\left\lfloor\frac{y}{b}\right\rfloor\) 相等的区间，设当 \(a \in [l_1, r_1], b \in [l_2, r_2]\) 时，\(t = \left\lfloor\frac{x}{a}\right\rfloor = \left\lfloor\frac{y}{b}\right\rfloor\)。那么我们有 \(b - a = \frac{y - x}{t}\)。显然 \(b - a \in [l_2 - r_1, l_1 - r_2]\)，若这个满足就可以构造一组解了。
注意构造完解后要判断是否满足 \(a > \sqrt{x} \land b > \sqrt{y}\)，还有别忘了 \(a, b\) 分别有 \(A, B\) 的上界。
时间复杂度 \(O(\sum \sqrt{\max(x, y)} \log \max(x, y))\)。
code
// Problem: J. X Equals Y
// Contest: Codeforces - The 2023 Guangdong Provincial Collegiate Programming Contest
// URL: https://codeforces.com/gym/104369/problem/J
// Memory Limit: 1024 MB
// Time Limit: 3000 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 double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
ll X, Y, A, B;
inline ll mysqrt(ll x) {
for (ll i = max((ll)sqrt(x) - 2, 0LL);; ++i) {
if (i * i > x) {
return i - 1;
}
}
}
void solve() {
scanf("%lld%lld%lld%lld", &X, &Y, &A, &B);
if (X == Y) {
puts("YES\n2 2");
return;
}
ll sx = mysqrt(X), sy = mysqrt(Y);
map<ll, pii> M;
for (ll i = 2, j; i <= X && i <= A; i = j + 1) {
j = X / (X / i);
M[X / i] = mkp(i, min(j, A));
}
for (ll i = 2, j; i <= Y && i <= B; i = j + 1) {
j = Y / (Y / i);
if (M.find(Y / i) == M.end()) {
continue;
}
ll t = Y / i;
ll l1 = M[t].fst, r1 = M[t].scd, l2 = i, r2 = min(j, B);
if ((Y - X) % t) {
continue;
}
ll d = (Y - X) / t;
if (l2 - r1 <= d && d <= r2 - l1) {
ll a = l1;
ll b = a + d;
if (b < l2) {
ll p = l2 - b;
a += p;
b += p;
}
if (a > sx && b > sy) {
printf("YES\n%lld %lld\n", a, b);
return;
}
}
}
map< vector<ll>, ll > mp;
for (ll a = 2; a <= A && a <= sx; ++a) {
vector<ll> vc;
ll x = X;
while (x) {
vc.pb(x % a);
x /= a;
}
reverse(vc.begin(), vc.end());
mp[vc] = a;
}
for (ll a = 2; a <= B && a <= sy; ++a) {
vector<ll> vc;
ll x = Y;
while (x) {
vc.pb(x % a);
x /= a;
}
reverse(vc.begin(), vc.end());
if (mp.find(vc) != mp.end()) {
printf("YES\n%lld %lld\n", mp[vc], a);
return;
}
}
puts("NO");
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}