题目解析

给定区间 $[l, r]$ 和目标最大公约数 $G$，需要找到两个数 $A$ 和 $B$（$l \le A \le B \le r$），使得 $\gcd(A, B) = G$，并且 $|A - B|$ 尽可能大。如果有多个解，选择 $A$ 最小的。

---

关键观察

1. 化简问题

如果 $\gcd(A, B) = G$，那么可以设 $A = G \cdot a$，$B = G \cdot b$，其中 $\gcd(a, b) = 1$。
此时 $a$ 和 $b$ 的范围为：

$$\left\lceil \frac{l}{G} \right\rceil \le a \le b \le \left\lfloor \frac{r}{G} \right\rfloor $$

原问题转化为：在区间 $[L, R]$ 内找两个互质的数 $a, b$（$L = \lceil l/G \rceil$，$R = \lfloor r/G \rfloor$），使得 $b - a$ 最大，且 $a$ 尽量小。

2. 贪心策略

为了最大化距离，我们想让 $a$ 尽量小，$b$ 尽量大，即尝试 $a = L$，$b = R$。

• 如果 $\gcd(L, R) = 1$，则 $(A, B) = (L \cdot G, R \cdot G)$ 即为答案。
• 否则，需要稍微调整 $a$ 或 $b$，使得它们互质。由于只相差一点点，距离几乎最大。

3. 调整范围

从最大距离开始，依次尝试距离减 $1$、减 $2$ 等。
对于距离 $d = R - L - k$，可能的数对为：

$$(L + i, R - (k - i)) \quad \text{for } i = 0,1,\dots,k $$

即固定 $a$ 和 $b$ 的和为 $L + R - k$，差值最大为 $R - L - k$。

因为 $L, R$ 可能很大（$10^{18}$ 级别），不能枚举所有 $k$。但可以证明，$k$ 只需要尝试到大约 $60$ 即可，因为当区间长度足够时，一定能找到互质对。

4. 为什么 $k$ 很小

在区间 $[L, L+30]$ 和 $[R-30, R]$ 中，一定存在一对互质的数（通过容斥原理可证）。
因此，最多需要尝试 $60$ 次距离递减（$k \le 60$），每次检查最多 $k+1$ 个数对，总复杂度 $O(60^2 \cdot \log)$ 可接受。

---

算法步骤

1. 读入 $l, r, G$。
2. 计算 $L = \lceil l / G \rceil$，$R = \lfloor r / G \rfloor$。
   若 $L > R$，则无解。
3. 从 $k = 0$ 开始，枚举距离减小量：
   • 尝试所有 $i = 0 \dots k$，设 $a = L + i$，$b = R - (k - i)$。
   • 检查是否 $L \le a \le b \le R$，且 $\gcd(a, b) = 1$。
   • 如果找到，输出 $A = a \cdot G$，$B = b \cdot G$。
4. 如果尝试完 $k = 0$ 到某个上限（如 $60$）仍未找到，输出 -1 -1。

---

时间复杂度

每个测试用例检查 $O(60^2) = 3600$ 个数对，每次检查 $\gcd$ 为 $O(\log)$，总复杂度 $O(t \cdot 3600 \cdot \log)$，$t \le 1000$ 可接受。

---

C++ 代码实现

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll gcd(ll a, ll b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

void solve() {
    ll l, r, g;
    cin >> l >> r >> g;
    
    // 找到区间内第一个和最后一个能被 g 整除的数
    ll L = (l + g - 1) / g;  // ceil(l / g)
    ll R = r / g;            // floor(r / g)
    
    if (L > R) {
        cout << "-1 -1\n";
        return;
    }
    
    // 尝试距离从大到小
    for (ll k = 0; k <= 60; k++) {
        // 距离 = R - L - k
        for (ll i = 0; i <= k; i++) {
            ll a = L + i;
            ll b = R - (k - i);
            if (a > b) continue;
            if (a < L || b > R) continue;
            if (gcd(a, b) == 1) {
                cout << a * g << " " << b * g << "\n";
                return;
            }
        }
    }
    
    cout << "-1 -1\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

验证样例

输入：

4
4 8 2
4 8 3
4 8 4
5 7 6

输出：

4 6
-1 -1
4 8
6 6

与题目输出一致。

---

补充说明

• 代码中 $k$ 的上限设为 $60$ 是安全的，实际所需往往更小。
• 注意使用 long long 避免溢出。
• 当 $G$ 很大时，$L$ 和 $R$ 可能很小，但算法依然正确。