Statistics

Problem Statement for "PointsOnCircle"

Problem Statement

You are given the radius r of a circle centered at the origin. Your task is to return the number of lattice points (points whose coordinates are both integers) on the circle. The number of pairs of integers (x, y) that satisfy x^2 + y^2 = n is given by the formula 4*(d1(n) - d3(n)), where di(n) denotes the number of divisors of n that leave a remainder of i when divided by 4.

Definition

Class:
PointsOnCircle
Method:
count
Parameters:
int
Returns:
long
Method signature:
long count(int r)
(be sure your method is public)

Constraints

  • r will be between 1 and 2*10^9, inclusive.

Examples

  1. 1

    Returns: 4

    The only lattice points on the circle are (0, 1), (1, 0), (-1, 0), (0, -1).

  2. 2000000000

    Returns: 76

  3. 3

    Returns: 4

    The number of lattice points on the circle of radius 3 is the same as the number of integer solutions of the equation x^2 + y^2 = 9. Using the formula from the problem statement we can calculate this number as 4*(d1(9) - d3(9)). It is easy to see that d1(9) = 2 (divisors 1 and 9) and d3(9) = 3 (divisor 3). So the answer is 4*(2 - 1) = 4.

  4. 1053

    Returns: 12

  5. 3511

    Returns: 4

  6. 1800000000

    Returns: 68

  7. 1610802055

    Returns: 36

  8. 967726946

    Returns: 12

  9. 1956400514

    Returns: 12

  10. 687035084

    Returns: 4

  11. 780165554

    Returns: 4

  12. 1520671607

    Returns: 108

  13. 614461065

    Returns: 36

  14. 262169838

    Returns: 4

  15. 1906812072

    Returns: 12

  16. 1084579707

    Returns: 36

  17. 1591193796

    Returns: 12

  18. 826600552

    Returns: 12

  19. 229633213

    Returns: 4

  20. 567776442

    Returns: 12

  21. 286623121

    Returns: 4

  22. 1805253983

    Returns: 36

  23. 598848701

    Returns: 12

  24. 44602633

    Returns: 12

  25. 602726579

    Returns: 36

  26. 1117197514

    Returns: 12

  27. 382256389

    Returns: 12

  28. 36664725

    Returns: 60

  29. 1099684835

    Returns: 12

  30. 706889153

    Returns: 12

  31. 871482254

    Returns: 12

  32. 1294084788

    Returns: 4

  33. 1652131677

    Returns: 12

  34. 575427533

    Returns: 4

  35. 1188230396

    Returns: 4

  36. 1076750517

    Returns: 4

  37. 605404020

    Returns: 36

  38. 1311801911

    Returns: 4

  39. 690533042

    Returns: 12

  40. 1935565234

    Returns: 4

  41. 431791902

    Returns: 12

  42. 1124142170

    Returns: 108

  43. 1879000545

    Returns: 36

  44. 993697882

    Returns: 36

  45. 1886788488

    Returns: 108

  46. 1370968819

    Returns: 12

  47. 1803071380

    Returns: 12

  48. 1727833033

    Returns: 12

  49. 665340066

    Returns: 12

  50. 592442990

    Returns: 12

  51. 1967262149

    Returns: 12

  52. 249420882

    Returns: 12

  53. 558096052

    Returns: 4

  54. 1041616440

    Returns: 12

  55. 737417579

    Returns: 4

  56. 85927249

    Returns: 36

  57. 2

    Returns: 4

  58. 1024

    Returns: 4

  59. 5

    Returns: 12

  60. 225

    Returns: 20

  61. 101

    Returns: 12

  62. 703096443

    Returns: 4

  63. 1021530510

    Returns: 324

  64. 132049

    Returns: 12

  65. 32045

    Returns: 324

  66. 160225

    Returns: 540

  67. 801125

    Returns: 756

  68. 1185665

    Returns: 972

  69. 5928325

    Returns: 1620

  70. 29641625

    Returns: 2268

  71. 48612265

    Returns: 2916

  72. 1745944200

    Returns: 180

  73. 243061325

    Returns: 4860

  74. 1999999973

    Returns: 12

  75. 1999999943

    Returns: 4

  76. 1998179401

    Returns: 20

  77. 1999073521

    Returns: 4

  78. 1215306625

    Returns: 6804

  79. 1000000000

    Returns: 76

  80. 1999999997

    Returns: 36

  81. 200000000

    Returns: 68

  82. 1073741818

    Returns: 12

  83. 12345678

    Returns: 12

  84. 1999999999

    Returns: 12

  85. 1803601800

    Returns: 100

  86. 199999999

    Returns: 36

  87. 1998756466

    Returns: 12

  88. 1234567891

    Returns: 4

  89. 1999998989

    Returns: 4

  90. 1000000007

    Returns: 4

  91. 1999999117

    Returns: 12

  92. 1999954997

    Returns: 12

  93. 1900105489

    Returns: 12

  94. 1999999990

    Returns: 108

  95. 1000000011

    Returns: 36

  96. 1991090304

    Returns: 4

  97. 25

    Returns: 20

  98. 67664141

    Returns: 12

  99. 1232424243

    Returns: 12

  100. 239017

    Returns: 12

  101. 1999999913

    Returns: 12

  102. 1000036819

    Returns: 4

  103. 1915351513

    Returns: 12

  104. 688294827

    Returns: 20

  105. 1000000009

    Returns: 12

  106. 1073741824

    Returns: 4

  107. 391252

    Returns: 12

  108. 1000000829

    Returns: 12

  109. 1868114

    Returns: 12

  110. 1259749573

    Returns: 12

  111. 1765092169

    Returns: 20

  112. 1931045213

    Returns: 12

  113. 1997333137

    Returns: 12

  114. 941474533

    Returns: 12

  115. 999999937

    Returns: 12

  116. 1003917915

    Returns: 108

  117. 1900000005

    Returns: 12

  118. 309522

    Returns: 12

  119. 21

    Returns: 4

  120. 654729075

    Returns: 180

  121. 51755357

    Returns: 12

  122. 46580625

    Returns: 180

  123. 1990000003

    Returns: 4

  124. 199785857

    Returns: 12

  125. 1389605779

    Returns: 4

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: