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

好耶 是ee的z

class Solution:

    def gcdOfOddEvenSums(self, n: int) -> int:

        return n



"""

n ** 2



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

n * (n + 1)



"""

等差数列求和 + 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);

    }

};

8点做的今日一题，和佬友的一样 ^-^

数学原理

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

class Solution:

    def gcdOfOddEvenSums(self, n: int) -> int:

        return n

class Solution:

    def gcdOfOddEvenSums(self, n: int) -> int:

        return n

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

我的脑子可能被僵尸吃了？ ^-^

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

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

数学不好。

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);

    }

};

原来直接返回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

    }

}

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)\)