Moe's CF Life

喵~ Programmer-san, konnichiwa! 我是你们的猫娘小助手，今天我们要一起解决一个关于最小公倍数 (LCM) 的有趣问题哦，喵~ 别担心，我会一步一步引导你，让问题变得像玩毛线球一样简单！

M. Minimum LCM 题解喵~

题目大意 (Problem Analysis)

题目给了我们一个整数 n，想让我们找到两个正整数 a 和 b，并且它们要满足 a + b = n。

在所有满足这个条件的 (a, b) 组合中，我们要找到那一对，使得它们的最小公倍数 LCM(a, b) 是最小的那个，然后把 a 和 b 输出出来就可以啦，喵~

比如 n=9，我们可以有 (1, 8), (2, 7), (3, 6), (4, 5) 这几对组合。它们的 LCM 分别是 LCM(1, 8)=8, LCM(2, 7)=14, LCM(3, 6)=6, LCM(4, 5)=20。最小的 LCM 是 6，所以答案就是 3 和 6 啦！

解题思路 (Solution Approach)

要让 LCM(a, b) 最小，我们得先知道它是个什么东西，对吧？有一个超级重要的公式：

LCM(a, b) = \frac{a \times b}{GCD(a, b)}

这里的 GCD(a, b) 是 a 和 b 的最大公约数哦。

因为题目告诉我们 a + b = n，所以 b = n - a。我们把这个代入上面的公式，就得到：

LCM(a, n - a) = \frac{a \times (n - a)}{GCD(a, n - a)}

这里有个小魔法！根据最大公约数的性质，GCD(a, n - a) 其实就等于 GCD(a, n) 啦（因为如果一个数能同时整除 a 和 n-a，那它也一定能整除它们的和 a + (n-a) = n）。

所以我们的目标变成了最小化：

\frac{a \times (n - a)}{GCD(a, n)}

要让一个分数变小，一个好办法就是让它的分母 GCD(a, n) 尽可能大！GCD(a, n) 是 n 的一个约数，所以我们希望 a 也是 n 的一个约数，这样它们的公约数才可能大呀。

接下来我们分两种情况讨论，就像猫咪看到黄瓜和看到小鱼干的反应是完全不同的一样，nya~

情况一：n 是偶数

这是最简单的情况！就像把偶数条小鱼干平分。我们可以让 a = n / 2，b = n / 2。

a + b = n/2 + n/2 = n，满足条件。
LCM(n/2, n/2) = n/2。

这个值已经是我们能达到的理论最小值了，因为 LCM(a, b) 至少要大于等于 a 和 b 中较大的那个，而 a 和 b 中至少有一个要大于等于 n/2。所以 n/2 就是最佳答案啦！

情况二：n 是奇数

奇数就稍微麻烦一点点，但别怕！我们刚才说了，要让分母 GCD(a, n) 尽可能大。那我们干脆就让 a 是 n 的一个约数吧！

假设 a 是 n 的一个约数，记作 d。那么 b = n - d。此时 GCD(a, b) = GCD(d, n - d) = d。所以 LCM(a, b) = (d \times (n - d)) / d = n - d。

看！我们的目标变成了最小化 n - d。要让这个值最小，我们就必须让 d 尽可能大！

d 是 n 的约数，而且 b 必须是正数 (b = n - d > 0)，所以 d 不能等于 n，只能是 n 的一个真约数（小于 n 的约数）。

那么，d 就是 n 的最大真约数！

一个数的最大真约数怎么求呢？就是用这个数除以它最小的那个质因数！

比如 n=9，最小质因数是 3，最大真约数就是 9/3=3。所以 a=3, b=9-3=6。
比如 n=35，最小质因数是 5，最大真约数就是 35/5=7。所以 a=7, b=35-7=28。

如果 n 本身就是个质数呢（比如 n=5）？那它最小的质因数就是它自己，最大真约数就是 1 啦。所以 a=1, b=5-1=4。

所以，对于奇数 n，我们只要找到它最小的质因数 p，那么 a = n / p，b = n - a 就是我们的答案了！

题解代码 (Solution Code)

下面我们来看看 C++ 代码是怎么实现这个思路的，喵~

cpp

#include <iostream>

// 这个函数用来解决单个测试用例
void solve() {
    int n;
    std::cin >> n;

    // 情况一：n 是偶数，就像我们分析的那样，直接对半分是最好的！
    if (n % 2 == 0) {
        std::cout << n / 2 << " " << n / 2 << "\n";
        return;
    }

    // 情况二：n 是奇数
    // 我们要找到 n 的最大真约数 a，然后 b = n - a
    // 这等价于找到 n 的最小质因数 p，然后 a = n / p

    int smallest_prime_factor = n; // 先假设 n 是质数，那么最小质因数就是它自己

    // 从 3 开始寻找 n 的最小质因数。
    // 因为 n 是奇数，它的质因数也肯定是奇数，所以我们只检查奇数（i += 2）
    // 检查到 sqrt(n) 就可以了，这是个优化的小技巧哦！
    for (long long i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            smallest_prime_factor = i; // 找到了！第一个找到的肯定是最小的
            break; // 找到就溜了，喵~
        }
    }

    // 如果循环结束 smallest_prime_factor 还是 n，说明 n 是个质数
    // 那么 a 就是 n / n = 1
    // 如果找到了更小的质因数 p，那么 a 就是 n / p
    int a = n / smallest_prime_factor;
    int b = n - a;
    std::cout << a << " " << b << "\n";
}

int main() {
    // 快速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

M. Minimum LCM 题解喵~ ​

题目大意 (Problem Analysis) ​

解题思路 (Solution Approach) ​

情况一：n 是偶数 ​

情况二：n 是奇数 ​

题解代码 (Solution Code) ​

相关知识点 (Knowledge Points) ​