自动搬运

查看原文

来自洛谷，原作者为

	EuphoricStar Remember.

搬运于2025-08-24 22:50:55，当前版本为作者最后更新于2023-10-04 07:35:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

当时在 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$ 时，我们有：

• $\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))$。

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