题目链接

游游的最小公倍数

题目描述

给定一个正整数 ，找到两个正整数 和 ，满足 ，并且使得它们的最小公倍数 尽可能大。输出这样的一组 和 。

解题思路

本题的目标是最大化 ，其中 。

我们首先利用最小公倍数和最大公因数的关系公式：

要最大化这个分式，我们需要同时考虑分子和分母：

  1. 最大化分子 ：对于一个固定的和 ，乘积 在 和 尽可能接近时取得最大值。也就是说， 和 应该在 附近。
  2. 最小化分母 ：最大公因数的最小可能值是 1。当 时，称 和 互质。

综合这两点，我们可以推断，要使 最大，我们应该优先寻找一对互质的数 ，因为此时分母 最小， 就等于乘积 。在所有互质的数对中，我们再选择乘积 最大的那一对，也就是 和 最接近 的那一对。

这就给出了一个清晰的贪心搜索策略：

  1. 从 的正中间开始，即令 ，。
  2. 检查当前的 和 是否互质，即 是否等于 1。
  3. 如果它们互质，那么我们已经找到了最接近中心的互质数对，它们的乘积在所有互质数对中是最大的。因此，这就是最优解。
  4. 如果它们不互质，我们就将 减 1， 加 1，然后重复第 2 步。我们不断地从中心向两边扩大搜索范围，直到找到第一对互质的数。由于 时，， 必定为 1，所以这个过程一定能找到解。

例如，对于 ：

  • 开始时，。。
  • 减 1，。。
  • 减 1，。。找到解，输出 3 和 7。

代码

#include <iostream>
#include <numeric> // C++17 for std::gcd, otherwise implement manually

using namespace std;

// 辗转相除法求最大公因数
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

void solve() {
    long long n;
    cin >> n;
    for (long long a = n / 2; a >= 1; --a) {
        long long b = n - a;
        if (gcd(a, b) == 1) {
            cout << a << " " << b << "\n";
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    // 辗转相除法求最大公因数
    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long n = sc.nextLong();
            for (long a = n / 2; a >= 1; --a) {
                long b = n - a;
                if (gcd(a, b) == 1) {
                    System.out.println(a + " " + b);
                    break;
                }
            }
        }
    }
}

import math

def solve():
    n = int(input())
    # 从 n/2 开始向下搜索 a
    for a in range(n // 2, 0, -1):
        b = n - a
        # 找到第一个互质的数对即为最优解
        if math.gcd(a, b) == 1:
            print(a, b)
            return

t = int(input())
for _ in range(t):
    solve()

算法及复杂度

  • 算法：贪心搜索 + 辗转相除法
  • 时间复杂度：，其中 是从 开始为了找到互质数对需要搜索的次数。由于互质数在整数中分布非常密集，所以 的期望值很小，算法效率非常高。
  • 空间复杂度：，只需要常数空间。