2026-10-31：数对的最大强度。用go语言，给定一个整数数组 nums。需要从数组中选出两个位置不同的元素，组成一个数对。该数对的强度等于：这两个元素的乘积，除以它们的最大公约数的平方。请计算并

2026-10-31：数对的最大强度。用go语言，给定一个整数数组 nums。需要从数组中选出两个位置不同的元素，组成一个数对。该数对的强度等于：这两个元素的乘积，除以它们的最大公约数的平方。请计算并返回所有可能数对中能够得到的最大强度值。

2 <= nums.length <= 2000。

1 <= nums[i] <= 100000。

输入： nums = [2,3,5]。

输出： 15。

解释：

选择 i = 1 和 j = 2，得到强度：

(3 * 5) / gcd(3, 5)2 = 15 / 1 = 15，这是所有数对中的最大值。

题目来自力扣4010。

大体步骤如下：

一、先看清"强度"这个式子的数学本质

数对 (x, y) 的强度定义为：

$$\text{strength}=\frac{x\cdot y}{\gcd (x,y{)}^2}$$

设 $g=\gcd (x,y)$，那么可以写成 $x=g\cdot a,y=g\cdot b$，且 $\gcd (a,b)=1$。代入后：

$$\frac{ga\cdot gb}{g^2}=a\cdot b=\frac{x}{g}\cdot \frac{y}{g}$$

结论：强度 = 两个数各自"约掉公因子之后"的乘积。 所以要让它大，需要两个条件同时满足：

顺带一个副产品：$x\cdot y$ 一定能被 $\gcd (x,y{)}^2$ 整除，所以代码里做整数除法 $\frac{xy}{g^2}$ 不会有任何取整误差，结果是精确的。这一点后面判断剪枝安全性时会用到。

题目数据范围 $n\le 2000$，两两数对一共约 $\frac{n(n-1)}{2}\approx 2\times 10^6$ 对，所以"全部枚举"本身是可行的baseline；这份代码的价值在于用一个上界剪枝把绝大多数情况压到远低于这个数。

二、整体策略：排序 + 构造一个"只依赖乘积"的上界

暴力枚举的问题是每一对都要算一次 $\gcd$。代码的思路是：

能不能在不算 $\gcd$ 的前提下，先判断"这一对绝对不可能刷新最优解"？如果能，就直接跳过不做 $\gcd$。

要做到这件事，需要两样东西：

• 一个便宜的上界：只靠 $x\cdot y$ 就能算出"这对的强度最多是多少"；
• 一个单调的枚举顺序：保证一旦上界跌破当前最优，后面所有候选只会更差，可以直接 break，而不是继续遍历。

排序负责第二件事，全局 $\gcd$ 负责第一件事。

三、步骤 1：降序排序（为单调性铺路）

代码用 slices.SortFunc 配合比较函数 b – a，把 nums 排成从大到小。

排序不是为了"找最大的两个数"这么简单（最大的两个数不一定是最优解，例如 [15, 10, 6] 中 15×10 的强度只有 6，而 10×6 的强度是 15）。排序的真正目的是让后面双重循环的枚举顺序具备单调性：

• 外层 i 递增时，$x=nums[i]$ 的值递减；
• 内层遍历 nums[:i]，即下标 $0,1,\dots ,i-1$，因为数组已降序，$y$ 的值也是递减的，而且恒有 $y\ge x$。

于是对固定的 $x$，内层循环中乘积 $x\cdot y$ 随着 $y$ 从 nums[0] 走到 nums[i-1] 是严格单调不增的。这个性质是 break 能够成立的前提。

补充一句副作用：这是原地排序，会直接打乱调用方传入的 slice 顺序；如果调用方还依赖原顺序，需要先拷贝一份。

四、步骤 2：求"全局 gcd"，构造合法上界

代码接着从头到尾把所有元素卷进一个 gcd，得到 allGcd，即整个数组所有元素的公共最大公约数，再平方得到 allGcd2。

初始值是 0，而 $\gcd (0,x)=x$（gcd 函数里 a = 0 时循环一次都不进，直接返回 b），所以第一次滚动等价于"把 allGcd 初始化成第一个元素"，这是标准的写法。由于 $\gcd$ 满足交换律和结合律，遍历顺序不影响结果。

关键的不等式推导：

$$\frac{x\cdot y}{\gcd (x,y{)}^2}\le \frac{x\cdot y}{{\text{allGcd}}^2}$$

右边就是那个"便宜的上界"——它完全不需要知道这一对具体的 $\gcd$，只要一次乘法一次除法就能算出来。而且它是"任意数对通用的"，对数组里所有数对同时成立。

还有个细节值得一提：$x\cdot y$ 未必能被 ${\text{allGcd}}^2$ 整除（因为 allGcd 只是 $g$ 的下界，不一定等于 $g$），所以 mul / allGcd2 是向下取整的整数除法。向下取整只会让这个上界更小（更紧），而不会让它失效——$\lfloor U\rfloor \le$ 真实强度 依然成立吗？这里要小心方向：真实强度 $\le \frac{xy}{{\text{allGcd}}^2}$（实数除法），而真实强度是整数，所以真实强度 $\le \lfloor \frac{xy}{{\text{allGcd}}^2}\rfloor$。是的，因为一个整数若不超过实数 $t$，那它也不超过 $\lfloor t\rfloor$。所以取整后的上界依然是合法上界，剪枝安全。

五、步骤 3：双重循环 + 上界剪枝

外层枚举 $i$（从 0 到 $n-1$），$x=nums[i]$；内层枚举 $j<i$，$y=nums[j]$。这样每个无序数对恰好被访问一次，不重不漏。

内层每一步做三件事：

这个 break 的正确性完全建立在第四节的继承和第三节的单调性之上，缺一不可：

• 没有单调的枚举顺序（比如乱序），即使某一对的上界不达标，也不能推断后面的对不达标，就只能 continue 而非 break，剪枝收益大打折扣；
• 没有合法上界，break 就可能把真正的答案剪掉。

六、用 nums = [2, 3, 5] 完整走一遍

验证一下被跳过的两对：$(2,5)$ 强度 10、$(2,3)$ 强度 6，确实都小于 15，剪枝没有剪错。

七、这个剪枝到底有多强？（以及什么时候会失效）

有意思的是，这个剪枝存在一个"两难"结构，让它在绝大多数输入下都异常高效：

• 如果数对的 $\gcd$ 普遍很小 → 强度值很大 → ans 迅速涨到一个很大的数 → 上界很容易就撞上 ans → 剪枝极早触发；
• 如果数对的 $\gcd$ 普遍很大 → 说明元素之间共享大量因子 → 全局 allGcd 也倾向于变大 → 上界 $\frac{xy}{{\text{allGcd}}^2}$ 被压得很低 → 上界本身就不容易超过 ans → 剪枝同样很早触发。

两个极端都利于剪枝，所以实践中内层循环往往每个 $i$ 只跑一两次就 break。

但它并非没有最坏情况：漏洞在于"全局 gcd 小、局部两两 gcd 大"的输入。典型构造是取一批大质数 $q_1\dots q_m$，令数组元素是这些质数的两两乘积 $q_i{q}_j$。任意两个元素共享一个质因子（局部 gcd ≈ 300），但任意三个元素的公共 gcd = 1（全局 allGcd = 1）。此时：

• 上界 $=x\cdot y\approx 10^5\times 10^5=10^{10}$，非常松；
• 而真实强度只有约 $q_j{q}_k\approx 10^5$，ans 很小；
• 于是上界几乎永远大于 ans，剪枝几乎完全失效，内层会跑满，退化成 $\mathcal{O}(n^2)$ 次完整枚举。

即便如此，$n=2000$ 时也就约 $2\times 10^6$ 次 $\gcd$，完全在限制内，所以这个上界分析上是 $\mathcal{O}(n^2)$、实践上远好于 $\mathcal{O}(n^2)$，属于"稳赚不赔"的优化。

八、复杂度分析

记 $n = $ 数组长度（$\le 2000$），$V=\max (nums)$（$\le 10^5$）。

时间复杂度

• 降序排序：$\mathcal{O}(n\log n)$（原地 pdqsort，比较函数 $\mathcal{O}(1)$）；
• 求全局 gcd：$n$ 次欧几里得，单次 $\mathcal{O}(\log V)$，合计 $\mathcal{O}(n\log V)$；
• 双重循环：迭代次数上界 $\frac{n(n-1)}{2}=\mathcal{O}(n^2)$。每次迭代是 $\mathcal{O}(1)$ 的乘法+比较，只有未触发剪枝的那些迭代才额外付一次 $\mathcal{O}(\log V)$ 的 $\gcd$。因此最坏 $\mathcal{O}(n^2\log V)$，剪枝生效时显著低于此。

总时间复杂度：$\mathcal{O}(n\log n+n^2\log V)$，由双重循环主导，即 $\mathcal{O}(n^2\log V)$。

由于 $V\le 10^5$，欧几里得的迭代轮数最多十几轮且常数极小，工程上可以直接视作 $\mathcal{O}(n^2)$；代入 $n=2000$ 即约 $2\times 10^6$ 次基本运算，毫秒级。

额外空间复杂度

• 排序是原地的，不分配新数组；nums[:i] 只是复用的切片头（三个机器字），循环中不产生堆分配；
• 排序递归栈 $\mathcal{O}(\log n)$；
• ans、allGcd、mul 等均为 $\mathcal{O}(1)$ 的标量。

总额外空间复杂度：$\mathcal{O}(\log n)$，全来自排序的递归栈；忽略栈则可视为 $\mathcal{O}(1)$。

九、两个实现层面的小提醒

Go完整代码如下：

package main

import (
"fmt"
"slices"
)

func maxPairStrength(nums []int) int64 {
slices.SortFunc(nums, func(a, b int) int { return b – a })

allGcd := 0
for _, x := range nums {
allGcd = gcd(allGcd, x)
}
allGcd2 := allGcd * allGcd

ans := 0
for i, x := range nums {
for _, y := range nums[:i] {
mul := x * y
if mul/allGcd2 <= ans {
break
}
g := gcd(x, y)
ans = max(ans, mul/(g*g))
}
}
return int64(ans)
}

func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}

func main() {
nums := []int{2, 3, 5}
result := maxPairStrength(nums)
fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from math import gcd

def max_pair_strength(nums):
# 按从大到小排序
nums.sort(reverse=True)

# 计算所有元素的整体 gcd
all_gcd = 0
for x in nums:
all_gcd = gcd(all_gcd, x)

all_gcd2 = all_gcd * all_gcd

ans = 0
for i, x in enumerate(nums):
for y in nums[:i]:
mul = x * y

if mul // all_gcd2 <= ans:
break

g = gcd(x, y)
ans = max(ans, mul // (g * g))

return ans

def main():
nums = [2, 3, 5]
result = max_pair_strength(nums)
print(result)

if __name__ == "__main__":
main()

C++完整代码如下：

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

int gcd_int(int a, int b) {
while (a != 0) {
int t = b % a;
b = a;
a = t;
}
return b;
}

long long maxPairStrength(vector<int> nums) {
sort(nums.begin(), nums.end(), greater<int>());

int allGcd = 0;
for (int x : nums) {
allGcd = gcd_int(allGcd, x);
}
long long allGcd2 = 1LL * allGcd * allGcd;

long long ans = 0;
for (int i = 0; i < (int)nums.size(); ++i) {
int x = nums[i];
for (int j = 0; j < i; ++j) {
int y = nums[j];
long long mul = 1LL * x * y;

if (mul / allGcd2 <= ans) {
break;
}

int g = gcd_int(x, y);
ans = max(ans, mul / (1LL * g * g));
}
}
return ans;
}

int main() {
vector<int> nums = {2, 3, 5};
long long result = maxPairStrength(nums);
cout << result << endl;
return 0;
}