Statistics

Problem Statement for "SparseFactorial"

Problem Statement

For an integer n, let F(n) = (n - 0^2) * (n - 1^2) * (n - 2^2) * (n - 3^2) * ... * (n - k^2), where k is the largest integer such that n - k^2 > 0. You are given three longs lo, hi and divisor. Compute and return the number of integers n between lo and hi, inclusive, such that F(n) is divisible by divisor.

Definition

Class:
SparseFactorial
Method:
getCount
Parameters:
long, long, long
Returns:
long
Method signature:
long getCount(long lo, long hi, long divisor)
(be sure your method is public)

Constraints

  • lo will be between 1 and 1,000,000,000,000, inclusive.
  • hi will be between lo and 1,000,000,000,000, inclusive.
  • divisor will be between 2 and 1,000,000, inclusive.

Examples

  1. 4

    8

    6

    Returns: 3

    The value of F(n) for each n = 4, 5, ..., 8 is as follows. F(4) = 4*3 = 12 F(5) = 5*4*1 = 20 F(6) = 6*5*2 = 60 F(7) = 7*6*3 = 126 F(8) = 8*7*4 = 224 Thus, F(4), F(6), F(7) are divisible by 6 but F(5) and F(8) are not.

  2. 9

    11

    7

    Returns: 1

    F(9) = 9*8*5 = 360 F(10) = 10*9*6*1 = 540 F(11) = 11*10*7*2 = 1540 Only F(11) is divisible by 7.

  3. 1

    1000000000000

    4

    Returns: 999999999996

    Watch out for the overflow.

  4. 55

    66

    98

    Returns: 7

  5. 12

    56

    100

    Returns: 24

  6. 999990

    999999

    589824

    Returns: 7

  7. 987654

    999999

    466273

    Returns: 33

  8. 10000

    20000

    749910

    Returns: 56

  9. 100000000

    100000050

    749910

    Returns: 8

  10. 7777777776

    7777777777

    994009

    Returns: 1

  11. 1

    1000000000000

    2

    Returns: 999999999999

  12. 2

    4

    2

    Returns: 3

  13. 1

    2

    2

    Returns: 1

  14. 1

    1000000000000

    3

    Returns: 666666666666

  15. 9

    11

    3

    Returns: 2

  16. 1

    1000000000000

    5

    Returns: 599999999998

  17. 2

    4

    5

    Returns: 0

  18. 430256012833

    522126424471

    5

    Returns: 55122246984

  19. 1

    1000000000000

    127

    Returns: 503937007169

  20. 646

    4903

    127

    Returns: 1693

  21. 13

    54

    127

    Returns: 0

  22. 556090189490

    909285533263

    127

    Returns: 177988204737

  23. 1

    1000000000000

    10009

    Returns: 500045778348

  24. 29872736

    83567163

    10009

    Returns: 26849921

  25. 347475261377

    750331738692

    10009

    Returns: 201448363351

  26. 1

    1000000000000

    943471

    Returns: 462911230218

  27. 40493145064

    259543837048

    943471

    Returns: 86925090547

  28. 1

    1000000000000

    907

    Returns: 500551233421

  29. 823519

    823555

    907

    Returns: 18

  30. 738965689595

    983111501027

    907

    Returns: 122207495465

  31. 1

    1000000000000

    30089

    Returns: 499978886995

  32. 1

    1000000000000

    981091

    Returns: 459894449904

  33. 1

    1000000000000

    1741

    Returns: 500287064537

  34. 267

    442

    1741

    Returns: 0

  35. 8119935522

    476513132719

    1741

    Returns: 234331117035

  36. 1

    1000000000000

    50077

    Returns: 499905484410

  37. 743654128

    1870342203

    50077

    Returns: 563355340

  38. 16725

    16790

    50077

    Returns: 0

  39. 2507711345

    2507723466

    50077

    Returns: 6080

  40. 1

    1000000000000

    978689

    Returns: 460090593060

  41. 299036254706

    920666555068

    978689

    Returns: 310815468016

  42. 1

    1000000000000

    999983

    Returns: 458334999443

  43. 530634775233

    816518820652

    999983

    Returns: 142942165507

  44. 50223

    133080

    999983

    Returns: 0

  45. 999966161702

    999966404242

    999983

    Returns: 121486

  46. 500287284924

    642912001972

    999983

    Returns: 71312429578

  47. 1

    1000000000000

    4

    Returns: 999999999996

  48. 1

    2

    4

    Returns: 0

  49. 761248560233

    857321798502

    4

    Returns: 96073238270

  50. 1

    1000000000000

    9

    Returns: 666666666663

  51. 534027352325

    787057794057

    9

    Returns: 168686961155

  52. 1

    1000000000000

    25

    Returns: 599999999990

  53. 428455519938

    948239345171

    25

    Returns: 311870295141

  54. 1

    1000000000000

    863041

    Returns: 500537960712

  55. 489

    731

    863041

    Returns: 0

  56. 863672

    863748

    863041

    Returns: 35

  57. 45922032959

    306927330897

    863041

    Returns: 130643125448

  58. 1

    1000000000000

    477481

    Returns: 500723449218

  59. 477959

    478159

    477481

    Returns: 99

  60. 1

    1000000000000

    4489

    Returns: 507462685209

  61. 3844

    4042

    4489

    Returns: 85

  62. 1

    59

    4489

    Returns: 0

  63. 4514

    4547

    4489

    Returns: 14

  64. 1

    1000000000000

    822649

    Returns: 500551027306

  65. 184897

    716988

    822649

    Returns: 121830

  66. 222

    402

    822649

    Returns: 0

  67. 112423525727

    703751954763

    822649

    Returns: 295990194907

  68. 1

    1000000000000

    383161

    Returns: 500807642224

  69. 480704670221

    817052797785

    383161

    Returns: 168445750484

  70. 1

    1000000000000

    16129

    Returns: 503937003074

  71. 46738530193

    858069963235

    16129

    Returns: 408859934764

  72. 1

    1000000000000

    966289

    Returns: 500508364419

  73. 245496

    862046

    966289

    Returns: 151826

  74. 614

    877

    966289

    Returns: 0

  75. 966326

    966601

    966289

    Returns: 147

  76. 306594626400

    854575449353

    966289

    Returns: 274269140279

  77. 1

    1000000000000

    358801

    Returns: 500834619442

  78. 35

    354

    358801

    Returns: 0

  79. 1

    1000000000000

    2809

    Returns: 509433961408

  80. 27

    37

    2809

    Returns: 0

  81. 1

    1000000000000

    524288

    Returns: 999999999238

  82. 2

    4

    524288

    Returns: 0

  83. 1

    1

    524288

    Returns: 0

  84. 5

    6

    524288

    Returns: 0

  85. 751083243730

    877392780842

    524288

    Returns: 126309537113

  86. 1

    1000000000000

    531441

    Returns: 666666666359

  87. 453248529858

    747758652425

    531441

    Returns: 196340081712

  88. 1

    1000000000000

    390625

    Returns: 599999999697

  89. 27

    30

    390625

    Returns: 0

  90. 245380356019

    374491162026

    390625

    Returns: 77466483606

  91. 1

    1000000000000

    510510

    Returns: 35540929655

  92. 103

    271

    510510

    Returns: 7

  93. 2

    5

    510510

    Returns: 0

  94. 293

    294

    510510

    Returns: 0

  95. 437833006747

    605973469455

    510510

    Returns: 5975868368

  96. 1

    1000000000000

    1000000

    Returns: 599999999844

  97. 6

    22

    1000000

    Returns: 0

  98. 25

    26

    1000000

    Returns: 0

  99. 1

    1000000000000

    392498

    Returns: 501128610600

  100. 1

    1000000000000

    784996

    Returns: 501128610600

  101. 196280

    196362

    784996

    Returns: 43

  102. 1

    1000000000000

    710649

    Returns: 334519557451

  103. 12603

    37392

    710649

    Returns: 1142

  104. 503597856411

    962377244114

    710649

    Returns: 153470684858

  105. 1

    1000000000000

    789610

    Returns: 301067601693

  106. 139

    187

    789610

    Returns: 0

  107. 642379083193

    655456545401

    789610

    Returns: 3937200370

  108. 1

    1000000000000

    999582

    Returns: 332564328026

  109. 6526111865

    7556510637

    999582

    Returns: 341402503

  110. 65106

    108114

    999582

    Returns: 0

  111. 27754647229

    27754705536

    999582

    Returns: 19402

  112. 528625105096

    662968065409

    999582

    Returns: 44781255434

  113. 1

    1000000000000

    999710

    Returns: 299753120845

  114. 2423533470

    8680371020

    999710

    Returns: 1876899821

  115. 54345

    61147

    999710

    Returns: 0

  116. 9994205794

    9994271397

    999710

    Returns: 19867

  117. 143930622022

    894274819621

    999710

    Returns: 225105511082

  118. 1

    1000000000000

    999819

    Returns: 332993491673

  119. 84915030184

    470851520001

    999819

    Returns: 128646654528

  120. 1

    1000000000000

    996709

    Returns: 285718476245

  121. 91992561

    211866914

    996709

    Returns: 34159007

  122. 413756565

    413763478

    996709

    Returns: 2013

  123. 1

    1000000000000

    996180

    Returns: 200007447807

  124. 275663371

    275672699

    996180

    Returns: 1862

  125. 696161306359

    941034409258

    996180

    Returns: 48977570245

  126. 123456789123

    987654321987

    999944

    Returns: 235918397150

  127. 123456789123

    987654321987

    998912

    Returns: 432320241954

  128. 123456789123

    987654321987

    997000

    Returns: 259519299243

  129. 123456789123

    987654321987

    994304

    Returns: 432543770311

  130. 123456789123

    987654321987

    984064

    Returns: 446037436318

  131. 387124612983

    988572894908

    238

    Returns: 181950740751

  132. 1

    100000050

    749910

    Returns: 11309424

  133. 1

    7777777777

    994009

    Returns: 3892498821

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: