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 |
| 0) | |
| | | Returns: 3 | | The possible sets are: {2}, {3}, {5}. |
|
|
| 1) | |
| | | Returns: 6 | | Here, {2,3}, {2,5} and {3,5} are also possible.
|
|
|
| 2) | |
| | | Returns: 7 | | The set {2,3,5} is added to the previous ones.
|
|
|
| 3) | |
| | | Returns: 9 | | Here, the sets are: {2}, {3}, {5}, {6}, {2,3}, {2,5}, {3,5}, {5,6}, {2,3,5}.
|
|
|
| 4) | |
| | |