Special Number

4.5

2 votes
Greedy Algorithms, Math, Algorithms, Basics of Greedy Algorithms
Problem

We are given an array nums of positive integers.
A special number is a number that is not divisible by the square of any number(>1).
Example:
12 is not a special number, because it is divisible by 4(which is 22).
18 is not a special number, because it is divisible by 9(which is 32).
35,6,15 are special numbers.
You have to find the number of the non-empty different subsets of the array such that the product of elements in it is a special number. Return answer modulo 109+7.

Input format

  • The first line contains an integer N, where N is denoting the size of the array.
  • The second line contains N space-separated integers denoting array nums.

Output format

  • Print the number of the non-empty different subsets.

Constraints

  • 1N4×104
  • 1nums[i]30
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

[2,3], [2,3], [2], [2], [3] are the possible subsets. So the answer is 5.

Editor Image

?