题解 | 游游的最小公倍数

#include <iostream>

int main() {
    int t;
  	std::cin >> t;
    while (t--) {
        long long n;
	  	std::cin >> n;
	 	// 特判 n = 2
        if (n == 2) std::cout << "1 1" << "\n";
	  	// n 为奇数
        else if (n & 1) std::cout << n / 2 << " " << n / 2 + 1 << "\n";  
	  	// n % 4 = 0
        else if (n % 4 == 0) std::cout << n / 2 - 1 << " " << n / 2 + 1 << "\n";
	  	// n % 4 == 2
        else std::cout << n / 2 - 2 << " " << n / 2 + 2 << "\n";
    }
    return 0;
}

对于两数 x, y ，互质时 lcm 最大，为 x * y。

由均值不等式，对于正实数 x, y, n 有 x + y = n，当 x = y = n / 2 时，x * y 最大，且当 x 和 y 越接近，乘积越大。

因 x, y 不是实数，且题目所求为其最大 lcm，故需要分类讨论。

n 为奇数规律容易发现，拆分为 floor(n / 2) 和 ceil(n / 2) 乘积最大，此时显然两数互质。

n 为偶数时，考虑 n % 4 = 0 和 n % 4 = 2 的两种情况。

先考虑 n % 4 = 0，若拆分成两个 n / 2 显然 lcm 不优，考虑拆成 n / 2 - 1 和 n / 2 + 1，此时拆分出的两奇数相差为 2 ，互质，则该情况为最优拆法。

再考虑 n % 4 = 2，此时有两种 lcm 最大的可能拆法，一种是拆成 n / 2 - 1 和 n / 2 + 1，一种是拆成 n / 2 - 2 和 n / 2 + 2。

第一种拆法会拆分出两个偶数，且相差为 2，则两数 gcd 为 2，则两数 lcm 为 (n / 2 - 1) * (n / 2 + 1) / 2 = (n ^ 2 / 4 - 1) / 2。

第二种拆法会拆分出两个奇数，且相差为 4，则两数互质，则两数 lcm 为 (n / 2 - 2) * (n / 2 + 2) = n ^ 2 / 4。

显然对于所有正整数 n，满足 n % 4 = 2，第二种拆法都更优。

但需要额外考虑 n = 2，此时 n / 2 - 2 < 0，不符题意，故需要特判，且 n = 2 的拆法有且仅有 {1, 1} 一种。