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

题目描述

给你一个整数 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^2\)，而前 \(n\) 个偶数的总和为 \(n(n + 1)\)。这两者的最大公约数至少为 \(n\)，又由于 \(n\) 和 \(n + 1\) 互质，因此答案就是 \(n\)。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

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

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

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

func gcdOfOddEvenSums(n int) int {
    return n
}

function gcdOfOddEvenSums(n: number): number {
    return n;
}

评论