GDCPC2023 J 题解

· · 题解

当时在 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) 的长度 = 1 时，x = y，可以直接判掉。

当 f(x, a) 的长度 = 2 时，我们有：

后者等价于 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))。

// 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;
}