LeetCode 解題筆記：3658. GCD of Odd and Even Sums

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


LeetCode 題目連結：3658. GCD of Odd and Even Sums

解題想法

簡單題。這題考數學，直接回傳 $n$ 即可。前 $n$ 個正的奇數和為 $$ sumOdd = 1 + 3 + 5 + \dots + (2n - 1) = \frac{(2n - 1 + 1) \times n}{2} = n^2 $$ 前 $n$ 個正的偶數和為 $$ sumEven = 2 + 4 + 6 + \dots + 2n = \frac{(2n + 2) \times n}{2} = n(n+1) $$ 因為 $n$ 與 $n+1$ 的最大公因數為 $1$，因此 $sumOdd$ 與 $sumEven$ 的最大公因數為 $n$。

如果沒有想到以上的數學性質，真的用迴圈算出 $sumOdd$ 與 $sumEven$ 的值再取最大公因數也可能，因為題目的 $n$ 最大為 $1000$，很快就能算完。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.18 MB, beats 85.77%.

class Solution:
    def gcdOfOddEvenSums(self, n: int) -> int:
        return n

Runtime: 11 ms, beats 38.21%. Memory: 19.24 MB, beats 53.03%.

class Solution:
    def gcdOfOddEvenSums(self, n: int) -> int:
        sumOdd = sum(range(1, 2*n, 2))
        sumEven = sum(range(2, 2*n + 1, 2))
        return gcd(sumOdd, sumEven)

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.52 MB, beats 46.67%.

class Solution {
public:
    int gcdOfOddEvenSums(int n) {
        return n;
    }
};

Runtime: 0 ms, beats 100.00%. Memory: 8.48 MB, beats 85.02%.

class Solution {
public:
    int gcdOfOddEvenSums(int n) {
        int sumOdd = 0, sumEven = 0;
        for(int i = 1; i < 2*n; i += 2) sumOdd += i;
        for(int i = 2; i <= 2*n; i += 2) sumEven += i;
        return gcd(sumOdd, sumEven);
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 9.13 MB, beats 16.92%.

int gcdOfOddEvenSums(int n) {
    return n;
}

Runtime: 0 ms, beats 100.00%. Memory: 9.00 MB, beats 89.62%.

int gcd(int a, int b) {
    int r;
    while(b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int gcdOfOddEvenSums(int n) {
    int sumOdd = 0, sumEven = 0;
    for(int i = 1; i < 2*n; i += 2) sumOdd += i;
    for(int i = 2; i <= 2*n; i += 2) sumEven += i;
    return gcd(sumOdd, sumEven);
}