number-of-different-subsequences-gcds

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an array <code>nums</code> that consists of positive integers.

The GCD of a sequence of numbers is defined as the greatest integer that divides all the numbers in the sequence evenly.

<ul>
	<li>For example, the GCD of the sequence <code>[4,6,16]</code> is <code>2</code>.</li>
</ul>

A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

<ul>
	<li>For example, <code>[2,5,10]</code> is a subsequence of <code>[1,2,1,2,4,1,5,10]</code>.</li>
</ul>

Return the number of different GCDs among all non-empty subsequences of <code>nums</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/17/image-1.png" style="width: 149px; height: 309px;" />
<pre>
Input: nums = [6,10,3]
Output: 5
Explanation: The figure shows all the non-empty subsequences and their GCDs.
The different GCDs are 6, 10, 3, 2, and 1.
</pre>

Example 2:

<pre>
Input: nums = [5,15,40,5,6]
Output: 7
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 2 * 105</code></li>
</ul>

第 235 场周赛

weekly-contest-235

countDifferentSubsequenceGCDs

高级专家

Number of Different Subsequences GCDs

Find Greatest Common Divisor of Array

find-greatest-common-divisor-of-array

找出数组的最大公约数

Array

Math

Counting

最大公约数

Number Theory

欧几里得算法

给你一个由正整数组成的数组 <code>nums</code> 。

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

<ul>
	<li>例如，序列 <code>[4,6,16]</code> 的最大公约数是 <code>2</code> 。</li>
</ul>

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

<ul>
	<li>例如，<code>[2,5,10]</code> 是 <code>[1,2,1,2,4,1,5,10]</code> 的一个子序列。</li>
</ul>

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

 

示例 1：
<img alt="" src="https://assets.leetcode.cn/aliyun-lc-upload/uploads/2021/04/03/image-1.png" />
<pre>
输入：nums = [6,10,3]
输出：5
解释：上图显示了所有的非空子序列与各自的最大公约数。
不同的最大公约数为 6 、10 、3 、2 和 1 。
</pre>

示例 2：

<pre>
输入：nums = [5,15,40,5,6]
输出：7
</pre>

 

提示：

<ul>
	<li><code>1 <= nums.length <= 105</code></li>
	<li><code>1 <= nums[i] <= 2 * 105</code></li>
</ul>