日期: 2026年7月16日

3867.数对的最大公约数之和

目标

给你一个长度为 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;
    }
}

性能