SquareFreeSets
SRM 440 · 2009-05-12 · by gojira_tc
SRM 440 · 2009-05-12 · by gojira_tc · Dynamic Programming, Math
Problem Statement
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 twoint s 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.
You are given two
Constraints
- N will be between 2 and 500, inclusive.
- K will be between 1 and 500, inclusive.
Examples
0)
5 1 Returns: 3
The possible sets are: {2}, {3}, {5}.
1)
5 2 Returns: 6
Here, {2,3}, {2,5} and {3,5} are also possible.
2)
5 3 Returns: 7
The set {2,3,5} is added to the previous ones.
3)
6 3 Returns: 9
Here, the sets are: {2}, {3}, {5}, {6}, {2,3}, {2,5}, {3,5}, {5,6}, {2,3,5}.
4)
28 41 Returns: 1599
Submissions are judged against all 121 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SquareFreeSets with a public method int countPerfect(int N, int K) · 121 test cases · 2 s / 256 MB per case