SquareFreeSets | Topcoder Archive

Problem Statement

A square-free number is an integer that is not divisible by the square of any integer except 1. A set containing only square-free numbers is called a square-free set. The product of such a set is the product of all its elements. If the product of a square-free set is a square-free number itself, that set is called a perfect set.

You are given two ints N and K. Determine the number of perfect square-free sets that contain between 1 and K elements, inclusive, where each element is between 2 and N, inclusive. Return this number modulo 1,000,000,007.

Definition

Class:: SquareFreeSets
Method:: countPerfect
Parameters:: int, int
Returns:: int
Method signature:: int countPerfect(int N, int K)
(be sure your method is public)

Constraints

N will be between 2 and 500, inclusive.
K will be between 1 and 500, inclusive.

Examples

```
5
```
```
1
```
```
Returns: 3
```
The possible sets are: {2}, {3}, {5}.
```
5
```
```
2
```
```
Returns: 6
```
Here, {2,3}, {2,5} and {3,5} are also possible.
```
5
```
```
3
```
```
Returns: 7
```
The set {2,3,5} is added to the previous ones.
```
6
```
```
3
```
```
Returns: 9
```
Here, the sets are: {2}, {3}, {5}, {6}, {2,3}, {2,5}, {3,5}, {5,6}, {2,3,5}.
```
28
```
```
41
```
```
Returns: 1599
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.