游游的最小公倍数

思路

题目在说什么？给一个正整数 ，要把它拆成两个正整数 （），让 尽可能大。

怎么让 lcm 最大？回忆一下，。所以我们想要两件事：

  1. 尽量大 —— 这意味着 和 尽量接近
  2. 尽量小 —— 最理想的情况是 （互质）

如果能找到一对互质的 且尽量靠近 ，那 就是最大的。

分情况讨论

是奇数：取 ，。这两个数是相邻整数，一定互质，乘积最大。

：取 ，。此时 是偶数，所以 和 都是奇数。它们的差为 2，且都是奇数，所以 但 必须是奇数，因此 。

且 ：取 行不行？不行，因为 是奇数， 和 都是偶数，。退一步，取 ，。此时 和 都是奇数（奇数减/加 2 还是奇数），差为 4， 必须是奇数且整除 4，所以 。

：只有 。

代码

#include <iostream>
using namespace std;

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        long long n;
        scanf("%lld", &n);
        long long 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 == 2){
                a = 1; b = 1;
            } else {
                a = n/2 - 2;
                b = n/2 + 2;
            }
        }
        printf("%lld %lld\n", a, b);
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            long n = sc.nextLong();
            long 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 == 2) {
                    a = 1;
                    b = 1;
                } else {
                    a = n / 2 - 2;
                    b = n / 2 + 2;
                }
            }
            sb.append(a).append(' ').append(b).append('\n');
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

def main():
    t = int(input())
    out = []
    for _ in range(t):
        n = int(input())
        if n % 2 == 1:
            a = n // 2
            b = n - a
        elif n % 4 == 0:
            a = n // 2 - 1
            b = n // 2 + 1
        else:
            if n == 2:
                a, b = 1, 1
            else:
                a = n // 2 - 2
                b = n // 2 + 2
        out.append(f"{a} {b}")
    print('\n'.join(out))

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    let idx = 0;
    const t = parseInt(lines[idx++]);
    const out = [];
    for (let i = 0; i < t; i++) {
        const n = BigInt(lines[idx++].trim());
        let a, b;
        if (n % 2n === 1n) {
            a = n / 2n;
            b = n - a;
        } else if (n % 4n === 0n) {
            a = n / 2n - 1n;
            b = n / 2n + 1n;
        } else {
            if (n === 2n) {
                a = 1n; b = 1n;
            } else {
                a = n / 2n - 2n;
                b = n / 2n + 2n;
            }
        }
        out.push(a.toString() + ' ' + b.toString());
    }
    console.log(out.join('\n'));
});

复杂度分析

  • 时间复杂度：，每组数据
  • 空间复杂度：

总结

这道题的核心是理解 ，要让 lcm 最大就要让 大（靠近中心）且 小（最好互质）。然后按 对 4 的余数分情况讨论，找到最靠近中心的互质对即可。每种情况都能在 内直接算出答案，整体思路清晰简洁。