题解 | #游游的最小公倍数#

问题分析

1. 数学模型

题目要求在满足 的正整数中，找到一组 使得 最大。 根据数论基础公式：

2. 优化目标分解

要使 最大，我们需要同时满足两个方向的优化：

1. 最大化分子 ：根据均值不等式，当和一定时，两个数越接近，乘积越大。因此 和 应当尽可能接近 。
2. 最小化分母 ：分母越小越好，最优情况是 ，即 与 互质。

数论构造 + 贪心策略

我们采用 数论构造 + 贪心策略。 我们的目标是从中心点 开始向外寻找最近的一对互质数 。根据 的奇偶性和对 4 的整除性，情况可以分为三类：

1. 情况一： 是奇数

• 构造：取 。
• 分析：此时 和 是相邻的整数（例如 ）。
• 证明：根据欧几里得算法原理，相邻整数互质，即 。
• 结果：分母为 1，分子取到了和固定情况下的最大乘积（最接近中心）。这是该情况下的理论最优解。

2. 情况二： 是偶数，且是 4 的倍数 ()

• 中点分析： 是偶数。如果取 ， 仅为 ，非常小。若取相邻 ，两者均为奇数。
• 构造：取 。
• 证明：
  • 设 为偶数。考察 。
  • 两者之差为 2。它们的公约数只能是 2 的约数（1 或 2）。
  • 因为 是偶数，所以 是奇数，不能被 2 整除。
  • 因此 。
• 结果：互质，乘积虽略小于中心平方，但分母为 1，整体最优。

3. 情况三： 是偶数，但不是 4 的倍数 ()

• 中点分析： 是奇数（例如 ）。
  • 尝试 ：由于 奇， 为偶，两个偶数的 至少为 2，导致 减半，非最优。
• 构造：再往外扩展一步，取 。
• 证明：
  • 设 为奇数。
  • 和 均为奇数。
  • 两者之差为 4。公约数只能是 4 的约数（1, 2, 4）。
  • 因为是奇数，排除 2 和 4。
  • 因此 。
  • (注：当 时，此逻辑会使 ，需特判或根据题目范围 ，由于 时解唯有 ，一般程序中 已经在奇偶处理中自然覆盖或作为边界处理，但严格数学上 是此逻辑的最小有效值，结果为 )
• 结果：互质，虽然乘积比除以 2 的情况小了一点，但避免了 减半的损失，优于 。

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        ll n;
        cin >> n;
        if (n == 2) {
            cout << 1 << " " << 1 << "\n";
            continue;
        }

        ll a, b;
        if (n % 2 == 1) {
            a = n / 2;
            b = n - a;
        } else if (n % 4 == 0) {
            a = n / 2 - 1;
            b = n / 2 + 1;
        } else if (n % 4 != 0) {
            a = n / 2 - 2;
            b = n / 2 + 2;
        }
        cout << a << " " << b << "\n";
    }
}