Statistics

Problem Statement for "SparseFactorialDiv2"

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. It is guaranteed that divisor will be a prime number. Compute and return the number of integers n between lo and hi, inclusive, such that F(n) is divisible by divisor.

Definition

Class:
SparseFactorialDiv2
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 997, inclusive.
  • divisor will be a prime number.

Examples

  1. 4

    8

    3

    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 3 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

    2

    Returns: 999999999999

    Watch out for the overflow.

  4. 16

    26

    11

    Returns: 4

  5. 10000

    20000

    997

    Returns: 1211

  6. 123456789

    987654321

    71

    Returns: 438184668

  7. 1

    1000000000000

    2

    Returns: 999999999999

  8. 3

    4

    2

    Returns: 2

  9. 1

    2

    2

    Returns: 1

  10. 2

    2

    2

    Returns: 1

  11. 5

    5

    2

    Returns: 1

  12. 370838091663

    834675418055

    2

    Returns: 463837326393

  13. 1

    1000000000000

    3

    Returns: 666666666666

  14. 3

    9

    3

    Returns: 5

  15. 1

    3

    3

    Returns: 1

  16. 3

    5

    3

    Returns: 2

  17. 9

    9

    3

    Returns: 1

  18. 9055532301

    996884473171

    3

    Returns: 658552627248

  19. 1

    1000000000000

    5

    Returns: 599999999998

  20. 13

    17

    5

    Returns: 3

  21. 1

    5

    5

    Returns: 1

  22. 4

    10

    5

    Returns: 4

  23. 26

    27

    5

    Returns: 1

  24. 379639826536

    866779149316

    5

    Returns: 292283593669

  25. 1

    1000000000000

    7

    Returns: 571428571425

  26. 24

    30

    7

    Returns: 4

  27. 1

    2

    7

    Returns: 0

  28. 5

    13

    7

    Returns: 3

  29. 49

    54

    7

    Returns: 4

  30. 207410943772

    620271392370

    7

    Returns: 235920256342

  31. 1

    1000000000000

    107

    Returns: 504672896695

  32. 2903

    4519

    107

    Returns: 815

  33. 17

    40

    107

    Returns: 0

  34. 148

    195

    107

    Returns: 3

  35. 11461

    11512

    107

    Returns: 29

  36. 147603225663

    380596911938

    107

    Returns: 117585598684

  37. 1

    1000000000000

    337

    Returns: 501483674710

  38. 29103

    86775

    337

    Returns: 28919

  39. 188

    247

    337

    Returns: 0

  40. 394

    563

    337

    Returns: 8

  41. 113758

    113793

    337

    Returns: 15

  42. 912777978662

    929259735768

    337

    Returns: 8265332200

  43. 1

    1000000000000

    487

    Returns: 501026684047

  44. 69498

    164388

    487

    Returns: 47539

  45. 147

    463

    487

    Returns: 0

  46. 438

    501

    487

    Returns: 4

  47. 237238

    237650

    487

    Returns: 206

  48. 320625606143

    400928202194

    487

    Returns: 40233744226

  49. 1

    1000000000000

    911

    Returns: 500548812613

  50. 525413

    828127

    911

    Returns: 151514

  51. 236

    596

    911

    Returns: 0

  52. 755

    1058

    911

    Returns: 13

  53. 830157

    830425

    911

    Returns: 138

  54. 175957449324

    696933000636

    911

    Returns: 260773711743

  55. 1

    1000000000000

    937

    Returns: 500533581123

  56. 75190

    132182

    937

    Returns: 19509

  57. 468

    736

    937

    Returns: 0

  58. 829

    1307

    937

    Returns: 20

  59. 878427

    878791

    937

    Returns: 175

  60. 49404831106

    726655676267

    937

    Returns: 338986815769

  61. 1

    1000000000000

    967

    Returns: 500517023885

  62. 182310

    563120

    967

    Returns: 189109

  63. 284

    727

    967

    Returns: 0

  64. 1246

    1775

    967

    Returns: 12

  65. 935481

    935520

    967

    Returns: 17

  66. 298893793182

    784617505894

    967

    Returns: 243113006143

  67. 1

    1000000000000

    997

    Returns: 500501462850

  68. 277346

    522107

    997

    Returns: 122495

  69. 233

    250

    997

    Returns: 0

  70. 603

    702

    997

    Returns: 0

  71. 994083

    994228

    997

    Returns: 72

  72. 183635036997

    394410526165

    997

    Returns: 105493449447

  73. 1

    999999999999

    17

    Returns: 529411764688

  74. 123456789000

    987654321000

    71

    Returns: 438184664115

  75. 179426549

    1000000000000

    997

    Returns: 500411701255

  76. 10000000000

    1000000000000

    2

    Returns: 990000000001

  77. 1

    1000000000000

    13

    Returns: 538461538452

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: