Number of Points Visible from the Origin
Time limit1sMemory limit128 MB
Count lattice points (x,y) with 0<=x,y<=N visible from the origin, meaning gcd(x,y)=1 or one coordinate is 0/1 edge case.
- Level
Medium4 of 10
- Topics
- Number theory, Math, Combinatorics
- Solved
- No attempts yet
Problem
Consider integer lattice points (x, y) on the coordinate plane such that 0 <= x, y <= N. The origin (0, 0) is not counted.
A point (x, y) is visible from the origin if the line segment from the origin to (x, y) does not pass through any other integer lattice point. For example, (4, 2) is not visible from the origin because the segment from (0, 0) to (4, 2) passes through (2, 1).
Given a positive integer N, count how many points (x, y) are visible from the origin.
Input
The first line contains the number of test cases C, where 1 <= C <= 1,000.
Each of the next C lines contains one test case. Each test case consists of one positive integer N, where 1 <= N <= 1,000.
Output
For each test case, output the number of points (x, y) visible from the origin on its own line.