3658.奇数和与偶数和的最大公约数：数论 / 数学O(1)

【LetMeFly】3658.奇数和与偶数和的最大公约数：数论 / 数学O(1)

力扣题目链接：https://leetcode.cn/problems/gcd-of-odd-and-even-sums/

给你一个整数 n。请你计算以下两个值的 最大公约数（GCD）：

• sumOdd：最小的 n 个正奇数的总和。

• sumEven：最小的 n 个正偶数的总和。

返回 sumOdd 和 sumEven 的 GCD。

 

示例 1：

输入： n = 4

输出： 4

解释：

• 前 4 个奇数的总和 sumOdd = 1 + 3 + 5 + 7 = 16
• 前 4 个偶数的总和 sumEven = 2 + 4 + 6 + 8 = 20

因此，GCD(sumOdd, sumEven) = GCD(16, 20) = 4。

示例 2：

输入： n = 5

输出： 5

解释：

• 前 5 个奇数的总和 sumOdd = 1 + 3 + 5 + 7 + 9 = 25
• 前 5 个偶数的总和 sumEven = 2 + 4 + 6 + 8 + 10 = 30

因此，GCD(sumOdd, sumEven) = GCD(25, 30) = 5。

 

提示：

• 1 <= n <= 1000

解题方法：数论 / 数学O(1)

首先计算sumOdd和sumEven：

• $sumOdd = 1 + 3 + 5 + \dots + 2n-1 = \frac{(1+2n-1)\times n}{2}=n\times n$
• $sumEven = 2 + 4 + 6 + \dots + 2n = \frac{(2+2n)\times n}2=n\times (n+1)$

解题方法一：数论算gcd

两个数的最大公约数 = 小数 和「大数 ÷ 小数的余数」的最大公约数。

算出$n^2$和$n\times (n+1)$的最大公约数(gcd)即可。

• 时间复杂度$O(\log n)$
• 空间复杂度$O(\log n)$

C++

/*
 * @LastEditTime: 2026-07-15 16:29:54
 */
/*
odd:  1 3 5 .. 2n-1 -> 2n * n / 2 = n^2
even: 2 4 6 ... 2n  -> (2n+2)*n/2 = n(n+1)
*/
class Solution {
private:
    int gcd(int a, int b) {
        return !b ? a : gcd(b, a % b);
    }
public:
    int gcdOfOddEvenSums(int n) {
        return gcd(n * n, n * (n + 1));
    }
};

解题方法二：一眼看出来结果（O(1)）

$n\times n$和$n\times(n+1)$的最大公约数是多少？首先不难看出它们有个公约数$n$，接着就是求$n$和$n+1$的最大公约数：

$n$和$n+1$的最大公约数一定是$1$，因为它们只相差了$1$。$a$和$b$的差值一定是其最大公约数的倍数。

所以我们直接返回$n$即可。

• 时间复杂度$O(1)$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-07-15 16:31:21
 */
/*
odd:  1 3 5 .. 2n-1 -> 2n * n / 2 = n^2
even: 2 4 6 ... 2n  -> (2n+2)*n/2 = n(n+1)
*/
class Solution {
public:
    int gcdOfOddEvenSums(int n) {
        return n;
    }
};

Python

'''
LastEditTime: 2026-07-15 16:32:26
'''
class Solution:
    def gcdOfOddEvenSums(self, n: int) -> int:
        return n

Java

/*
 * @LastEditTime: 2026-07-15 16:32:05
 */
class Solution {
    public int gcdOfOddEvenSums(int n) {
        return n;
    }
}

Go

/*
 * @LastEditTime: 2026-07-15 16:31:45
 */
package main

func gcdOfOddEvenSums(n int) int {
    return n
}

Rust

/*
 * @LastEditTime: 2026-07-15 16:32:48
 */
impl Solution {
    pub fn gcd_of_odd_even_sums(n: i32) -> i32 {
        n
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源