题解 | 游游的最小公倍数

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

// lcm = a / gcd * b; 目标让gcd尽可能小，a*b尽可能大，a*b要大那么必定先从n/2附近开始查找
// 而gcd要小那么就是要ab互质，此时gcd=1
// 优先确保gcd=1，因为a*b的值变化只能算是微调，而gcd从1变成2，对lcm的变化是极为显著的
// 那么思路就是从n/2开始向两端查找满足互质的数对，即为答案
// 知识点：辗转相除法，基于lcm公式的贪心搜索法

// 过程：以a = n/2 为起点向前for循环自减遍历，b在每次循环也随之更新，利用辗转相除法求得最大公约数
// 如果gcd == 1，那么找到满足条件的数对，直接输出ab，退出循环；
// 否则继续以上遍历，直到a == 1，b = n-1，此时gcd必定为1

void solve() {
    long long n;
    cin >> n;
    // 下面使用辗转相除法找出ab的最大公因数
    for (long long a = n / 2; a >= 1; a--) {
        long long b = n - a;
        long long a1 = a;
        long long b1 = b;
        long long r = a1 % b1;
        while (r != 0) {
            a1 = b1;
            b1 = r;
            r = a1 % b1;
        }
        long long gcd = b1;
        if (gcd == 1) {
            cout << a << " " << b << '\n';
            return;
        }
    }
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}