目标
给你一个长度为 n 的整数数组 nums。
构造一个数组 prefixGcd，其中对于每个下标 i：
- 令 mxi = max(nums[0], nums[1], ..., nums[i])。
- prefixGcd[i] = gcd(nums[i], mxi)。
在构造 prefixGcd 之后：
- 将 prefixGcd 按 非递减 顺序排序。
- 通过取 最小的未配对 元素和 最大的未配对 元素来形成数对。
- 重复此过程，直到无法再形成更多数对。
- 对于每个形成的数对，计算 两个元素的最大公约数 gcd。
- 如果 n 是奇数，prefixGcd 数组中的 中间 元素保持 未配对 状态，并应被忽略。
返回一个整数，表示所有形成数对的 最大公约数之和。
术语 gcd(a, b) 表示 a 和 b 的 最大公约数。
示例 1：
输入： nums = [2,6,4]
输出： 2
解释：
构造 prefixGcd：
i nums[i] mxi prefixGcd[i]
0 2 2 2
1 6 6 6
2 4 6 2
prefixGcd = [2, 6, 2]。排序后形成 [2, 2, 6]。
将最小和最大的元素配对：gcd(2, 6) = 2。剩下的中间元素 2 被忽略。因此，总和为 2。示例 2：
输入： nums = [3,6,2,8]
输出： 5
解释：
构造 prefixGcd：
i nums[i] mxi prefixGcd[i]
0 3 3 3
1 6 6 6
2 2 6 2
3 8 8 8
prefixGcd = [3, 6, 2, 8]。排序后形成 [2, 3, 6, 8]。
形成数对：gcd(2, 8) = 2 和 gcd(3, 6) = 3。因此，总和为 2 + 3 = 5。说明：
- 1 <= n == nums.length <= 10^5
- 1 <= nums[i] <= 10^9
思路
有一个正整数数组 nums，构造数组 prefixGcd，prefixGcd[i] = gcd(maxi, nums[i])，其中 maxi 为 [0, i] 的最大值。将 prefixGcd 排序后首尾配对，忽略中间未配对元素，求每对 gcd 之和。
根据题目模拟即可。
代码
/**
* @date 2026-07-16 9:34
*/
public class GcdSum3867 {
public long gcdSum(int[] nums) {
int n = nums.length;
int[] prefixGcd = new int[n];
int max = 0;
for (int i = 0; i < n; i++) {
max = Math.max(max, nums[i]);
prefixGcd[i] = gcd(max, nums[i]);
}
Arrays.sort(prefixGcd);
long res = 0;
int l = 0, r = n - 1;
while (l < r) {
res += gcd(prefixGcd[l++], prefixGcd[r--]);
}
return res;
}
public int gcd(int a, int b) {
while (b != 0) {
int tmp = b;
b = a % b;
a = tmp;
}
return a;
}
}
性能
