Q2. Sum of GCD of Formed Pairs

📘 題目敘述

給你一個長度為 n 的整數陣列 nums。

請先建立一個陣列 prefixGcd，對每個 index i：

令 mxi = max(nums[0], nums[1], ..., nums[i])
prefixGcd[i] = gcd(nums[i], mxi)

建立完 prefixGcd 後：

先將 prefixGcd 依非遞減順序排序
然後每次取目前最小的未配對元素和最大的未配對元素配成一組
重複這個動作，直到不能再配對為止

對每一組配對，計算這兩個數的 gcd。

如果 n 是奇數，排序後中間那個元素不會被配對，直接忽略。

請回傳所有配對的 gcd 值總和。

gcd(a, b) 表示 a 和 b 的最大公因數。

條件限制

1 <= n == nums.length <= 10^5
1 <= nums[i] <= 10^9

🧠 解題思路

這題照題目要求一步一步做就可以。

整體分成三段：

先建出 prefixGcd
把 prefixGcd 排序
用雙指標從最小和最大往中間配對，累加每組的 gcd

先看第一段。

題目定義：

mxi 是前綴最大值
prefixGcd[i] = gcd(nums[i], mxi)

所以我在掃 nums 的時候，會一路維護目前前綴最大值 mxi。
每到一個位置 i：

先更新 mxi = max(mxi, nums[i])
再算 pfg[i] = gcd(nums[i], mxi)

這樣 pfg 就是題目要的 prefixGcd。

接著第二段，把 pfg 排序。

排序之後，題目說配對方式是：

最小的配最大的
次小的配次大的
一直做下去

所以第三段就很自然地用雙指標：

l 指向最左邊
r 指向最右邊

每次把：

gcd(pfg[l], pfg[r])

加進答案，然後：

l++
r--

如果長度是奇數，最後中間那個元素會自己剩下來，而 while (l < r) 本來就不會去配它，所以剛好符合題意。

也就是說，這題的核心就是：

先依題意建出 prefixGcd，排序後再用雙指標從兩端往中間配對並累加每組的 gcd。

所有變數

n：陣列長度
pfg：題目中的 prefixGcd 陣列
mxi：目前掃到位置 i 時，前綴 nums[0...i] 的最大值
ans：所有配對 gcd 的總和
l：排序後 pfg 的左指標，指向目前最小的未配對元素
r：排序後 pfg 的右指標，指向目前最大的未配對元素

🪜 主要流程步驟

1. 先準備 prefixGcd 陣列和前綴最大值

int n = nums.size();
vector<int> pfg(n);
int mxi = INT_MIN;

這裡：

n 是陣列長度
pfg 用來存題目要的 prefixGcd
mxi 用來記目前前綴中的最大值

一開始 mxi 先設成很小，之後每掃到一個元素就更新。

2. 掃一次 nums，依題意建出 prefixGcd

for (int i = 0; i < n; i++) {
    mxi = max(mxi, nums[i]);
    pfg[i] = gcd(nums[i], mxi);
}

這一步是照題目定義直接做。

對每個位置 i：

mxi = max(mxi, nums[i])
- 把目前前綴最大值更新好
pfg[i] = gcd(nums[i], mxi)
- 這就是題目定義的 prefixGcd[i]

例如如果前面最大值一路變成：

那對應位置就會分別去算：

gcd(nums[i], 2)
gcd(nums[i], 6)
gcd(nums[i], 6)

這樣整個 pfg 就建好了。

3. 把 prefixGcd 排序

sort(pfg.begin(), pfg.end());

因為題目接下來要求的配對方式是：

最小的未配對元素
配最大的未配對元素

所以一定要先排序。

排序完之後，整個配對順序就很清楚了。

4. 用雙指標從最左和最右開始配對

long long ans = 0;
int l = 0, r = n - 1;
while (l < r) {
    ans += gcd(pfg[l], pfg[r]);
    l++;
    r--;
}

這一段是在做題目指定的配對方式。

l 指向目前最小的未配對元素
r 指向目前最大的未配對元素

每次都把這兩個數配成一組，並把它們的 gcd 加到 ans 裡。

然後：

l++
r--

表示這一組已經配完，改處理下一組。

如果 n 是奇數，最後會剩下一個中間元素：

例如 l == r

但因為迴圈條件是 while (l < r)，所以那個中間元素不會被拿去配對，剛好符合題目要求「中間元素忽略」。

5. 最後回傳答案

return ans;

當所有可以配對的元素都處理完後，ans 就是所有 formed pairs 的 gcd 總和，直接回傳即可。

⏱️ 複雜度

設 n = nums.length。

時間複雜度：O(n log n)
建立 prefixGcd 需要掃一次陣列，排序需要 O(n log n)，最後雙指標再掃一半，整體由排序主導。
空間複雜度：O(n)
額外使用了一個長度為 n 的 pfg 陣列。

💻 程式碼實作

class Solution {
public:
    long long gcdSum(vector<int>& nums) {
        int n = nums.size();
        vector<int> pfg(n);
        int mxi = INT_MIN;
        for (int i = 0; i < n; i++) {
            mxi = max(mxi, nums[i]);
            pfg[i] = gcd(nums[i], mxi);
        }
        sort(pfg.begin(), pfg.end());
        long long ans = 0;
        int l = 0, r = n - 1;
        while (l < r) {
            ans += gcd(pfg[l], pfg[r]);
            l++;
            r--;
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/contest/biweekly-contest-178/problems/sum-of-gcd-of-formed-pairs/