3658. 奇数和偶数和的最大公约数

Easy

题目描述

给定一个整数 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

解题思路

这道题目表面上看起来需要计算前 n 个奇数和偶数的和，然后求最大公约数。但通过数学分析，我们可以找到一个优雅的规律。

首先分析奇数和偶数的求和公式：

• 前 n 个奇数：1, 3, 5, …, (2n-1)，这是一个等差数列，和为 n²
• 前 n 个偶数：2, 4, 6, …, 2n，这是一个等差数列，和为 n(n+1)

所以问题转化为求 GCD(n², n(n+1)) = GCD(n², n(n+1))。

利用最大公约数的性质：GCD(a, b) = GCD(a, b-a)，我们有： GCD(n², n(n+1)) = GCD(n², n(n+1) - n²) = GCD(n², n) = n

这是因为 n² 显然是 n 的倍数，所以 GCD(n², n) = n。

另一种理解方式是：GCD(n², n(n+1)) = n × GCD(n, n+1)，而连续两个整数的最大公约数总是1，所以结果就是 n。

因此，答案直接就是 n，无需进行复杂的计算。

代码实现

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

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

public class Solution {
    public int GcdOfOddEvenSums(int n) {
        return n;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var gcdOfOddEvenSums = function(n) {
    return n;
};

复杂度分析