LeetCode 解題筆記：3867. Sum of GCD of Formed Pairs

作者：王一哲
日期：2026年7月16日


LeetCode 題目連結：3867. Sum of GCD of Formed Pairs

解題想法

中等難度的題目。題目給一個長度為 $n$ 的陣列 $nums$，依序取 $nums$ 前綴的最大值，並將最大值與 $nums[i]$ 取最大公因數，填入陣列 $prefixGcd$。填完 $prefixGcd$ 之後，將 $prefixGcd$ 由小到大排序。最後由 $prefixGcd$ 兩端往中央取值，計算 $prefixGcd[i], prefixGcd[n-i-1]$ 的最大公因數，將最大公因數加總求答案。只要按照題目的規則寫程式就好，不需要想太多。

Python 程式碼

Runtime: 187 ms, beats 75.45%. Memory: 34.02 MB, beats 37.13%.

class Solution:
    def gcdSum(self, nums: list[int]) -> int:
        # 計算 prefixGcd 再排序
        n = len(nums)
        imax = nums[0]
        prefixGcd = [imax] + [0] * (n-1)
        for i in range(1, n):
            imax = max(imax, nums[i])
            prefixGcd[i] = gcd(nums[i], imax)
        prefixGcd.sort()
        
        # 由 prefixGcd 兩端向中央取值，計算兩者的 gcd 再相加
        ans = 0
        for i in range(n//2):
            ans += gcd(prefixGcd[i], prefixGcd[n-i-1])
        return ans

C++ 程式碼

Runtime: 67 ms, beats 85.87%. Memory: 155.67 MB, beats 75.58%.

class Solution {
public:
    long long gcdSum(vector<int>& nums) {
        // 計算 prefixGcd 再排序
        int n = (int)nums.size(), imax = nums[0];
        vector<int> prefixGcd (n, 0);
        prefixGcd[0] = imax;
        for(int i = 1; i < n; i++) {
            imax = max(imax, nums[i]);
            prefixGcd[i] = gcd(nums[i], imax);
        }
        sort(prefixGcd.begin(), prefixGcd.end());
        
        // 由 prefixGcd 兩端向中央取值，計算兩者的 gcd 再相加
        long long ans = 0;
        for(int i = 0; i < n/2; i++) {
            ans += gcd(prefixGcd[i], prefixGcd[n-i-1]);
        }
        return ans;
    }
};