Leetcode每日一题 —— 3658. 奇数和与偶数和的最大公约数

开发调优
,
1

思路

求和+求公约数。什么时候做困难题也能像做简单题这么轻松就好了~

代码

class Solution {
    public int gcdOfOddEvenSums(int n) {
        int sumOdd = (1 + 2 * n - 1) * n / 2;
        int sumEven = (2 + 2 * n) * n / 2;
        return gcd(sumOdd, sumEven);
    }
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = a;
            a = b;
            b = temp % b;
        }
        return a;
    }
}
5 个赞
2

好耶 是ee的z

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


"""
n ** 2

n * (2*n + 2) // 2
n * (n + 1)

"""
2 个赞
3

等差数列求和 + GCD 最小公约数

另外才发现 GCD 函数里不需要先尝试交换 a, b，如果 a<b，第一次迭代会自动交换

class Solution {
public:
    int gcdOfOddEvenSums(int n) {
        // 等差数列求和
        // Sn = a1 + a1+d + a1+2*d + ... + a1+(n-1)*d
        //    = n*a1 + (1+2+...+(n-1))*d
        //    = n*a1 + n(n-1)/2 * d
        int sumOdd=1*n + n*(n-1);
        int sumEven=2*n + n*(n-1);
        auto gcd=[&](int a, int b)->int {
            if(a<b){
                swap(a,b);
            }
            while(a%b>0){
                int temp=a%b;
                a=b;
                b=temp;
            }
            return b;
        };
        return gcd(sumOdd,sumEven);
    }
};
3 个赞
4

8点做的今日一题，和佬友的一样 :laughing:

图片
图片1017×431 9.47 KB

2 个赞
5

数学原理

算术评级3 第 464 场周赛 Q1 难度分 1220

class Solution:
    def gcdOfOddEvenSums(self, n: int) -> int:
        return n
2 个赞
6 
class Solution:
    def gcdOfOddEvenSums(self, n: int) -> int:
        return n
1 个赞
7

看了佬友的解答，回去仔细一看，一个是n×n 一个是 n×(n+1)。果然直接返回n就是了

我的脑子可能被僵尸吃了？ :upside_down_face:

1 个赞
8

我直接当数学题先算完化简了，本来还打算写个gcd一看发现不对劲，发现根本不用写 :tieba_002:

4 个赞
9

突然发现一个事，这个是不是直接return n就行了

1 个赞
10

数学不好。

class Solution {
public:
    int gcdOfOddEvenSums(int n) {
        int sumodd = 0, sumeven = 0;
        auto gcd = [&](this auto&& gcd, int a, int b) -> int {
            return b ? gcd(b, a%b) : a;
        };
        for(int i = 1; i <= 2 * n; i++) {
            if(i % 2) {
                sumodd += i;
            }  else {
                sumeven += i;
            }
        }
        return gcd(sumodd,sumeven);
    }
};
1 个赞
11

原来直接返回n就行了吗…
就我傻傻的模拟了一遍吗…

impl Solution {
    pub fn gcd_of_odd_even_sums(n: i32) -> i32 {
        let mut odd: i32 = 0;
        let mut eve: i32 = 0;
        for i in 1..n * 2 + 1 {
            if i % 2 == 0 {
                eve += i;
            } else {
                odd += i;
            }
        }
        let mut s = if odd < eve { odd } else { eve };
        while odd % s != 0 || eve % s != 0 {
            s -= 1;
        }
        s
    }
}
1 个赞
12

gpt回答的，哈哈

关键是推导两个数的和：

  • 前 \(n\) 个正奇数之和：\(\text{sumOdd}=n^2\)
  • 前 \(n\) 个正偶数之和：\(\text{sumEven}=n(n+1)\)

因此：

\[ \gcd(n^2,n(n+1)) = n\cdot \gcd(n,n+1) = n \]

因为相邻两个整数 \(n\) 和 \(n+1\) 一定互质，所以答案直接返回 n。

C++

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

Python

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

时间复杂度：\(O(1)\)
空间复杂度：\(O(1)\)

1 个赞