此题是幼儿园难题，但不是幼儿园难度。

我们先把题目简化，假设有一个函数 $\operatorname{d(x)}$，其用于求 $x$ 的约数个数。那么要求的就是 $\operatorname{d(x)} + \operatorname{d(y)} - \operatorname{d(\gcd(x,y))}$ 的最大值，且满足 $1 \le x,y \le n$。想要求最大值明显要满足两个条件：

1. $\operatorname{d(x)}$ 和 $\operatorname{d(y)}$ 要尽可能地大；
2. $\operatorname{d(\gcd(x,y))}$ 要尽可能地小。

但同时满足两个条件有些困难，所以我们考虑先满足条件一，但这样可能并不能“精准命中”答案，所以我们要多计算几组 $x$ 和 $y$。接着再两两比较，看谁更满足条件二，这样就能在时间范围内求得答案啦。

具体怎么实现呢？首先，我们用深搜来构造 $x$（$y$ 可以看作另一个构造出来的 $x'$），对于每个 $x$，$\operatorname{d(x)}$ 想要尽可能大，要满足两个条件：

1. 质因子只能是连续的小质数；
2. 质因子的指数是非递增的。

:::info[证明] 对于第一个，可以举例子：比如说有一个数 $2^a \times 7^b$，改为 $2^a \times 5^b$ 值更小，还多了更多的空间装下别的因数。

第二个也可以举例子：比如 $2^4 \times 3^1$ 和 $2^1 \times 3^3$，前者不仅值更小，因数个数还更多，明显优于后者。 :::

但是，由于前文的条件二的限制，所以这里的条件二并不总是起作用，甚至会漏掉正确答案，所以我们只能使用条件一。

接下来讲下深搜：我们要记录三个值：深度 $k$，目前数的值 $x$ 以及 $x$ 的约数个数 $d$。在提前筛出的质数表中枚举因子 $p$ 和对应的指数 $e$。当使用完质数表中所有的质数后，将满足要求的 $x$ 和 $d$ 放入一个优先队列中，以节省时间和空间（详细解释看代码），对应代码如下：

int p[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};//质数表
int lim[15] = {44, 24, 13, 9, 6, 5, 4, 3, 2, 1, 1, 1, 1, 1, 1};//用于剪枝的，后面再讲
priority_queue<pair<int, ll>> q;
int need = 500;//构造 500 个 x 用于两两配对
void dfs (int k, ll x, int d) {
	if (k == 15) {//使用完了整个质数表
		if (q.size() < need)//未超过 500 个就放入队列中
			q.push({-d, x});
		else if (d > -q.top().first) {//如果新的超过 500 个但更优
			q.pop();//把 500 组中最劣的弹出
			q.push({-d, x}); //放入新的
		} 
		return;
	}
	dfs(k + 1, x, d);//一个质因子不选
	int e = 0;
	ll y = x;
	while (y <= n / p[k] && e < lim[k]) {//枚举选 p 这个数当因子 e 次
		y *= p[k];
		e++;
		dfs(k + 1, y, d * (e + 1));
	}
}

现在我们有了 $x$、$y$、$\operatorname{d(x)}$ 和 $\operatorname{d(y)}$，还差 $\gcd(x,y)$ 和 $\operatorname{d(\gcd(x,y))}$，前者有现成的，也就是说我们还需要一个函数 $\operatorname{d(x)}$ 的具体实现代码，如下：

int d (ll x) {
	int res = 1;
	for (int i = 0; i < 15; i++) {
		if ((ll)p[i] * p[i] > x)//如果 p[i] * p[i] 大于 x，说明后面没有（或只有一个）质因数了，跳出去单独判断
			break;
		int e = 0;
		while (x % p[i] == 0) {//计算有多少个质因数
			e++;
			x /= p[i];
		}
		res *= (e + 1);//增加对应的约数个数
	}
	if (x > 1)//单独判断还有没有质因数
		res *= 2;
	return res;//返回总的约数个数
}

最后在比较之后输出最优的答案就行了。然后讲一下前文的 $lim_k$ 是干嘛的：这是我随便设的一个数组，满足 ${p_k}^{lim_k + 10} \approx 10^{16}$，放上去竟然解决了代码的时间超限问题（也许未来会有数据卡掉这种操作？）。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
int p[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
int lim[15] = {44, 24, 13, 9, 6, 5, 4, 3, 2, 1, 1, 1, 1, 1, 1};
int need = 500;
priority_queue<pair<int, ll>> q;
void dfs (int k, ll x, int d) {
	if (k == 15) {
		if (q.size() < need)
			q.push({-d, x});
		else if (d > -q.top().first) {
			q.pop();
			q.push({-d, x}); 
		} 
		return;
	}
	dfs(k + 1, x, d);
	int e = 0;
	ll y = x;
	while (y <= n / p[k] && e < lim[k]) {
		y *= p[k];
		e++;
		dfs(k + 1, y, d * (e + 1));
	} 
}
int d (ll x) {
	int res = 1;
	for (int i = 0; i < 15; i++) {
		if ((ll)p[i] * p[i] > x)
			break;
		int e = 0;
		while (x % p[i] == 0) {
			e++;
			x /= p[i];
		}
		res *= (e + 1);
	}
	if (x > 1)
		res *= 2;
	return res;
}
int main () {
    cin >> n;
    dfs(0, 1, 1);
    vector<pair<int, ll>> s;//创建一个数组 s 代替队列 q，这样更好遍历
    while (!q.empty()) {//把 q 中的数据放入 s
    	s.push_back(q.top());
    	q.pop();
	}
	need = min(need, (int)s.size());//在一些小数据中，500 个可能都多了，所以要动态调整限制
	ll ansx, ansy, ans = -1e18;
	for (int i = 0; i < need; i++) {//枚举 + 选择，得到最优答案
		ll x = s[i].second;
		int dx = -s[i].first;
		for (int j = i; j < need; j++) {
			ll y = s[j].second;
			int dy = -s[j].first;
			ll g = __gcd(x, y);
			int dg = d(g);
			if (dx + dy - dg > ans) {
				ans = dx + dy - dg;
				ansx = x;
				ansy = y;
			}
		} 
	}
	cout << ans << '\n' << ansx << ' ' << ansy;//输出答案
    return 0;
}

这是一位自宅警备员的第九篇题解，可以点个赞吗求求了