Problem : Maximum GCD Pair / 最大公约数对

任务总览表

题目描述

给定一个正整数 N，请找到 1 到 N 之间的两个不同整数 (x, y)，使得 gcd(x, y) 的值尽可能大，并输出这个最大公约数的值。

输入格式

输入包含一个正整数 N，保证 2 <= N <= 1000000。

输出格式

输出一个整数，表示在 1 到 N 之间，两个不同整数的最大公约数的最大值。

样例输入 1

10

样例输出 1

5

​解释​：选取 (5, 10)，gcd(5, 10) = 5，这是 1 到 10 之间可能得到的最大公约数。

样例输入 2

12

样例输出 2

6

​解释​：选取 (6, 12)，gcd(6, 12) = 6，这是 1 到 12 之间可能得到的最大公约数。

提示

• gcd(x, y) 表示 x 和 y 的最大公约数。
• 选择 (N // 2, N) 这两个数通常能得到最大的 gcd(x, y)，因为 gcd(N // 2, N) = N // 2。
• 计算 gcd(x, y) 可使用 ​**辗转相除法（欧几里得算法）**​，时间复杂度为 O(log N)。

题目分析

​目标​：在 1 到 N 之间，找到两个不同整数，使得它们的最大公约数最大。 ​思路​：

• 观察 gcd(x, N)，当 x = N // 2 时，通常 gcd(x, N) = N // 2 是最大值。
• 直接输出 N // 2 作为答案。

时间复杂度分析

• 计算 N // 2 只需 O(1) 的时间，因此该方法可以在 ​1 秒内高效运行​。

结论

• 该问题利用了 gcd(x, y) 的性质，找到 N 在 [1, N] 内的最佳约数对。
• 只需计算 N // 2 即可得到答案，避免暴力遍历所有可能的 (x, y) 组合。