Statistics

Problem Statement for "SquareFreeSets"

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

  1. 5

    1

    Returns: 3

    The possible sets are: {2}, {3}, {5}.

  2. 5

    2

    Returns: 6

    Here, {2,3}, {2,5} and {3,5} are also possible.

  3. 5

    3

    Returns: 7

    The set {2,3,5} is added to the previous ones.

  4. 6

    3

    Returns: 9

    Here, the sets are: {2}, {3}, {5}, {6}, {2,3}, {2,5}, {3,5}, {5,6}, {2,3,5}.

  5. 28

    41

    Returns: 1599

  6. 2

    1

    Returns: 1

  7. 2

    2

    Returns: 1

  8. 3

    1

    Returns: 2

  9. 3

    2

    Returns: 3

  10. 4

    1

    Returns: 2

  11. 4

    2

    Returns: 3

  12. 10

    1

    Returns: 6

  13. 10

    3

    Returns: 22

  14. 19

    6

    Returns: 514

  15. 19

    7

    Returns: 526

  16. 19

    8

    Returns: 527

  17. 20

    1

    Returns: 12

  18. 20

    2

    Returns: 65

  19. 20

    7

    Returns: 526

  20. 25

    4

    Returns: 703

  21. 30

    5

    Returns: 2129

  22. 31

    5

    Returns: 3362

  23. 31

    11

    Returns: 6655

  24. 31

    30

    Returns: 6655

  25. 50

    18

    Returns: 217087

  26. 52

    100

    Returns: 241663

  27. 53

    500

    Returns: 483327

  28. 54

    6

    Returns: 101352

  29. 77

    2

    Returns: 877

  30. 77

    7

    Returns: 2780581

  31. 90

    16

    Returns: 401466010

  32. 90

    23

    Returns: 410124286

  33. 100

    1

    Returns: 60

  34. 100

    11

    Returns: 396162793

  35. 100

    30

    Returns: 184890872

  36. 101

    9

    Returns: 160354310

  37. 101

    217

    Returns: 369781745

  38. 133

    22

    Returns: 919816342

  39. 140

    2

    Returns: 2836

  40. 143

    5

    Returns: 6547947

  41. 149

    12

    Returns: 934469273

  42. 150

    66

    Returns: 216547409

  43. 171

    4

    Returns: 1386007

  44. 171

    5

    Returns: 14866231

  45. 171

    8

    Returns: 273252649

  46. 171

    17

    Returns: 242687948

  47. 171

    100

    Returns: 560722957

  48. 180

    3

    Returns: 107872

  49. 180

    23

    Returns: 236303590

  50. 199

    30

    Returns: 675949811

  51. 199

    31

    Returns: 549627783

  52. 199

    61

    Returns: 561216532

  53. 200

    44

    Returns: 561216429

  54. 201

    1

    Returns: 122

  55. 201

    2

    Returns: 5834

  56. 201

    3

    Returns: 156176

  57. 201

    4

    Returns: 2777475

  58. 201

    5

    Returns: 35930774

  59. 201

    10

    Returns: 680094343

  60. 201

    19

    Returns: 297753758

  61. 250

    6

    Returns: 273671628

  62. 250

    12

    Returns: 622456092

  63. 250

    19

    Returns: 767284319

  64. 288

    1

    Returns: 176

  65. 288

    8

    Returns: 929484630

  66. 288

    20

    Returns: 214979107

  67. 288

    53

    Returns: 302173652

  68. 289

    1

    Returns: 176

  69. 289

    2

    Returns: 12064

  70. 289

    30

    Returns: 681974323

  71. 289

    40

    Returns: 247719734

  72. 289

    68

    Returns: 504131194

  73. 299

    23

    Returns: 166018334

  74. 299

    34

    Returns: 899354107

  75. 300

    50

    Returns: 77423504

  76. 300

    125

    Returns: 532876911

  77. 300

    500

    Returns: 532876911

  78. 302

    6

    Returns: 46613614

  79. 302

    15

    Returns: 456487101

  80. 311

    2

    Returns: 14080

  81. 311

    13

    Returns: 890742119

  82. 311

    73

    Returns: 166937251

  83. 320

    4

    Returns: 18125207

  84. 333

    41

    Returns: 824243233

  85. 333

    60

    Returns: 922474248

  86. 340

    29

    Returns: 167455959

  87. 350

    300

    Returns: 608483469

  88. 361

    1

    Returns: 218

  89. 361

    2

    Returns: 18547

  90. 361

    6

    Returns: 712602321

  91. 361

    50

    Returns: 202406534

  92. 361

    126

    Returns: 68935461

  93. 400

    5

    Returns: 86754309

  94. 400

    18

    Returns: 365058783

  95. 401

    17

    Returns: 27831151

  96. 410

    21

    Returns: 595242627

  97. 410

    25

    Returns: 87250417

  98. 420

    30

    Returns: 220202719

  99. 430

    3

    Returns: 1497405

  100. 441

    4

    Returns: 63348791

  101. 441

    27

    Returns: 288920433

  102. 456

    1

    Returns: 278

  103. 456

    76

    Returns: 365037057

  104. 492

    500

    Returns: 638909183

  105. 493

    8

    Returns: 981256579

  106. 493

    409

    Returns: 521680420

  107. 494

    21

    Returns: 19103265

  108. 498

    3

    Returns: 2378973

  109. 498

    26

    Returns: 187129846

  110. 498

    499

    Returns: 529982055

  111. 499

    4

    Returns: 107376919

  112. 499

    45

    Returns: 923357053

  113. 499

    220

    Returns: 59964104

  114. 500

    1

    Returns: 305

  115. 500

    2

    Returns: 36163

  116. 500

    5

    Returns: 484973720

  117. 500

    17

    Returns: 183569777

  118. 500

    34

    Returns: 145016606

  119. 500

    92

    Returns: 59938211

  120. 500

    500

    Returns: 59964104

  121. 500

    300

    Returns: 59964104

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.
This problem was used for: