Connection Status:
Competition Arena > PointsOnCircle

PointsOnCircle

SRM 365 · 2007-09-12 · by Xixas

SRM 365 · 2007-09-12 · by Xixas · Math, Simple Search, Iteration
Class Name: PointsOnCircle
Return Type: long
Method Name: count
Arg Types: (int)
Problem Statement

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.

Constraints

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

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
1
Returns: 4

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

1)
2000000000
Returns: 76
2)
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.

3)
1053
Returns: 12
4)
3511
Returns: 4

Submissions are judged against all 125 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PointsOnCircle with a public method long long count(int r) · 125 test cases · 2 s / 256 MB per case

Submitting as anonymous