count-the-number-of-square-free-subsets

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a positive integer 0-indexed&nbsp;array <code>nums</code>.

A subset of the array <code>nums</code> is square-free if the product of its elements is a square-free integer.

A square-free integer is an integer that is divisible by no square number other than <code>1</code>.

Return the number of square-free non-empty subsets of the array nums. Since the answer may be too large, return it modulo <code>109 + 7</code>.

A non-empty&nbsp;subset of <code>nums</code> is an array that can be obtained by deleting some (possibly none but not all) elements from <code>nums</code>. Two subsets are different if and only if the chosen indices to delete are different.

&nbsp;
Example 1:

<pre>
Input: nums = [3,4,4,5]
Output: 3
Explanation: There are 3 square-free subsets in this example:
- The subset consisting of the 0th element [3]. The product of its elements is 3, which is a square-free integer.
- The subset consisting of the 3rd element [5]. The product of its elements is 5, which is a square-free integer.
- The subset consisting of 0th and 3rd elements [3,5]. The product of its elements is 15, which is a square-free integer.
It can be proven that there are no more than 3 square-free subsets in the given array.</pre>

Example 2:

<pre>
Input: nums = [1]
Output: 1
Explanation: There is 1 square-free subset in this example:
- The subset consisting of the 0th element [1]. The product of its elements is 1, which is a square-free integer.
It can be proven that there is no more than 1 square-free subset in the given array.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length&nbsp;&lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 30</code></li>
</ul>

squareFreeSubsets

Count the Number of Square-Free Subsets

Distinct Prime Factors of Product of Array

distinct-prime-factors-of-product-of-array

数组乘积中的不同质因数数目

Bit Manipulation

Array

Math

Dynamic Programming

Bitmask

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

如果数组 <code>nums</code> 的子集中的元素乘积是一个 无平方因子数 ，则认为该子集是一个 无平方 子集。

无平方因子数 是无法被除 <code>1</code> 之外任何平方数整除的数字。

返回数组 <code>nums</code> 中 无平方 且 非空 的子集数目。因为答案可能很大，返回对 <code>109 + 7</code> 取余的结果。

<code>nums</code> 的 非空子集 是可以由删除 <code>nums</code> 中一些元素（可以不删除，但不能全部删除）得到的一个数组。如果构成两个子集时选择删除的下标不同，则认为这两个子集不同。

&nbsp;

示例 1：

<pre>
输入：nums = [3,4,4,5]
输出：3
解释：示例中有 3 个无平方子集：
- 由第 0 个元素 [3] 组成的子集。其元素的乘积是 3 ，这是一个无平方因子数。
- 由第 3 个元素 [5] 组成的子集。其元素的乘积是 5 ，这是一个无平方因子数。
- 由第 0 个和第 3 个元素 [3,5] 组成的子集。其元素的乘积是 15 ，这是一个无平方因子数。
可以证明给定数组中不存在超过 3 个无平方子集。</pre>

示例 2：

<pre>
输入：nums = [1]
输出：1
解释：示例中有 1 个无平方子集：
- 由第 0 个元素 [1] 组成的子集。其元素的乘积是 1 ，这是一个无平方因子数。
可以证明给定数组中不存在超过 1 个无平方子集。</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length&nbsp;&lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 30</code></li>
</ul>