How can I calculate the number of different GCDs from subsequences efficiently?

Focus on using dynamic programming or optimized set-based calculations that avoid brute-force enumeration of all subsequences.

What is the main challenge in solving the "Number of Different Subsequences GCDs" problem?

The main challenge lies in efficiently calculating subsequences' GCDs without overcomplicating the solution or exceeding time limits.

What should I consider when approaching this problem's optimization?

Consider utilizing properties of divisibility and GCD to minimize redundant checks and iterating efficiently over the array.

How does number theory apply to this problem?

Number theory helps by leveraging divisibility rules and GCD properties to efficiently determine the number of distinct GCD values.

Can GhostInterview assist with understanding GCD properties for subsequences?

Yes, GhostInterview provides insights into the mathematical approach for optimizing GCD calculations, ensuring an efficient solution.

#1819

Hard

auto_awesome数组·数学

LeetCode 题解工作台

序列中不同最大公约数的数目

给你一个由正整数组成的数组 nums 。数字序列的最大公约数定义为序列中所有整数的共有约数中的最大整数。例如，序列 [4,6,16] 的最大公约数是 2 。数组的一个子序列本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。例如， [2,5,10] 是 [1,2,1, 2…

数组数学计数数论

题目描述

给你一个由正整数组成的数组 nums 。

数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。

例如，序列 [4,6,16] 的最大公约数是 2 。

数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。

例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。

计算并返回 nums 的所有非空子序列中不同最大公约数的数目。

示例 1：

输入：nums = [6,10,3]
输出：5
解释：上图显示了所有的非空子序列与各自的最大公约数。
不同的最大公约数为 6 、10 、3 、2 和 1 。

示例 2：

输入：nums = [5,15,40,5,6]
输出：7

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 2 * 10⁵

lightbulb

解题思路

方法一：枚举 + 数学

对于数组 $nums$ 的所有子序列，其最大公约数一定不超过数组中的最大值 $mx$ 。

因此我们可以枚举 $[1,.. mx]$ 中的每个数 $x$ ，判断 $x$ 是否为数组 $nums$ 的子序列的最大公约数，如果是，则答案加一。

那么问题转换为：判断 $x$ 是否为数组 $nums$ 的子序列的最大公约数。我们可以通过枚举 $x$ 的倍数 $y$ ，判断 $y$ 是否在数组 $nums$ 中，如果 $y$ 在数组 $nums$ 中，则计算 $y$ 的最大公约数 $g$ ，如果出现 $g = x$ ，则 $x$ 是数组 $nums$ 的子序列的最大公约数。

时间复杂度 $O(n + M \times \log M)$ ，空间复杂度 $O(M)$ 。其中 $n$ 和 $M$ 分别是数组 $nums$ 的长度和数组 $nums$ 中的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
        mx = max(nums)
        vis = set(nums)
        ans = 0
        for x in range(1, mx + 1):
            g = 0
            for y in range(x, mx + 1, x):
                if y in vis:
                    g = gcd(g, y)
                    if g == x:
                        ans += 1
                        break
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to optimize solutions using number theory principles.
question_mark
Efficiency in handling large input sizes and array lengths.
question_mark
Understanding of dynamic programming or optimization strategies.

warning

常见陷阱

外企场景

error
Attempting to brute-force through all subsequences without leveraging mathematical properties.
error
Overlooking optimizations related to divisibility and GCD calculation.
error
Not handling large input sizes efficiently, leading to time limit exceeded errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
How does the problem change if we are given an array of size 10^6?
arrow_right_alt
What if the array only contains powers of two?
arrow_right_alt
How does the problem behave with very large numbers up to 2 * 10^5?

help

常见问题

外企场景

继续练习

#1994 好子集的数目 #2001 可互换矩形的组数 #914 卡牌分组