Skip to content

Latest commit

 

History

History
234 lines (181 loc) · 5.96 KB

README.md

File metadata and controls

234 lines (181 loc) · 5.96 KB
Raw
comments difficulty edit_url rating source tags
true
中等
1518
第 421 场周赛 Q1
数组
数学
数论

3334. 数组的最大因子得分

English Version

题目描述

给你一个整数数组 nums。

因子得分 定义为数组所有元素的最小公倍数（LCM）与最大公约数（GCD）的 乘积。

在 最多 移除一个元素的情况下，返回 nums 的 最大因子得分。

注意，单个数字的 LCM 和 GCD 都是其本身，而 空数组 的因子得分为 0。

 

示例 1：

输入： nums = [2,4,8,16]

输出： 64

解释：

移除数字 2 后，剩余元素的 GCD 为 4，LCM 为 16，因此最大因子得分为 4 * 16 = 64。

示例 2：

输入： nums = [1,2,3,4,5]

输出： 60

解释：

无需移除任何元素即可获得最大因子得分 60。

示例 3：

输入： nums = [3]

输出： 9

 

提示：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 30

解法

方法一

Python3

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        n = len(nums)
        suf_gcd = [0] * (n + 1)
        suf_lcm = [0] * n + [1]
        for i in range(n - 1, -1, -1):
            suf_gcd[i] = gcd(suf_gcd[i + 1], nums[i])
            suf_lcm[i] = lcm(suf_lcm[i + 1], nums[i])
        ans = suf_gcd[0] * suf_lcm[0]
        pre_gcd, pre_lcm = 0, 1
        for i, x in enumerate(nums):
            ans = max(ans, gcd(pre_gcd, suf_gcd[i + 1]) * lcm(pre_lcm, suf_lcm[i + 1]))
            pre_gcd = gcd(pre_gcd, x)
            pre_lcm = lcm(pre_lcm, x)
        return ans

Java

class Solution {
    public long maxScore(int[] nums) {
        int n = nums.length;
        long[] sufGcd = new long[n + 1];
        long[] sufLcm = new long[n + 1];
        sufLcm[n] = 1;
        for (int i = n - 1; i >= 0; --i) {
            sufGcd[i] = gcd(sufGcd[i + 1], nums[i]);
            sufLcm[i] = lcm(sufLcm[i + 1], nums[i]);
        }
        long ans = sufGcd[0] * sufLcm[0];
        long preGcd = 0, preLcm = 1;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, gcd(preGcd, sufGcd[i + 1]) * lcm(preLcm, sufLcm[i + 1]));
            preGcd = gcd(preGcd, nums[i]);
            preLcm = lcm(preLcm, nums[i]);
        }
        return ans;
    }

    private long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    private long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }
}

C++

class Solution {
public:
    long long maxScore(vector<int>& nums) {
        int n = nums.size();
        vector<long long> sufGcd(n + 1, 0);
        vector<long long> sufLcm(n + 1, 1);
        for (int i = n - 1; i >= 0; --i) {
            sufGcd[i] = gcd(sufGcd[i + 1], nums[i]);
            sufLcm[i] = lcm(sufLcm[i + 1], nums[i]);
        }

        long long ans = sufGcd[0] * sufLcm[0];
        long long preGcd = 0, preLcm = 1;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, gcd(preGcd, sufGcd[i + 1]) * lcm(preLcm, sufLcm[i + 1]));
            preGcd = gcd(preGcd, nums[i]);
            preLcm = lcm(preLcm, nums[i]);
        }
        return ans;
    }
};

Go

func maxScore(nums []int) int64 {
	n := len(nums)
	sufGcd := make([]int64, n+1)
	sufLcm := make([]int64, n+1)
	sufLcm[n] = 1
	for i := n - 1; i >= 0; i-- {
		sufGcd[i] = gcd(sufGcd[i+1], int64(nums[i]))
		sufLcm[i] = lcm(sufLcm[i+1], int64(nums[i]))
	}

	ans := sufGcd[0] * sufLcm[0]
	preGcd, preLcm := int64(0), int64(1)
	for i := 0; i < n; i++ {
		ans = max(ans, gcd(preGcd, sufGcd[i+1])*lcm(preLcm, sufLcm[i+1]))
		preGcd = gcd(preGcd, int64(nums[i]))
		preLcm = lcm(preLcm, int64(nums[i]))
	}
	return ans
}

func gcd(a, b int64) int64 {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func lcm(a, b int64) int64 {
	return a / gcd(a, b) * b
}

TypeScript

function maxScore(nums: number[]): number {
    const n = nums.length;
    const sufGcd: number[] = Array(n + 1).fill(0);
    const sufLcm: number[] = Array(n + 1).fill(1);
    for (let i = n - 1; i >= 0; i--) {
        sufGcd[i] = gcd(sufGcd[i + 1], nums[i]);
        sufLcm[i] = lcm(sufLcm[i + 1], nums[i]);
    }

    let ans = sufGcd[0] * sufLcm[0];
    let preGcd = 0,
        preLcm = 1;
    for (let i = 0; i < n; i++) {
        ans = Math.max(ans, gcd(preGcd, sufGcd[i + 1]) * lcm(preLcm, sufLcm[i + 1]));
        preGcd = gcd(preGcd, nums[i]);
        preLcm = lcm(preLcm, nums[i]);
    }
    return ans;
}

function gcd(a: number, b: number): number {
    return b === 0 ? a : gcd(b, a % b);
}

function lcm(a: number, b: number): number {
    return (a / gcd(a, b)) * b;
}