1971F.md (1147B)
1 Source: https://codeforces.com/problemset/problem/1971/F 2 3 F. Circle Perimeter 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Given an integer $r$, find the number of lattice points that have a Euclidean distance from $(0, 0)$ greater than or equal to $r$ but strictly less than $r+1$. 22 23 A lattice point is a point with integer coordinates. The Euclidean distance from $(0, 0)$ to the point $(x,y)$ is $\sqrt{x^2 + y^2}$. 24 25 Input 26 27 The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. 28 29 The only line of each test case contains a single integer $r$ ($1 \leq r \leq 10^5$). 30 31 The sum of $r$ over all test cases does not exceed $10^5$. 32 33 Output 34 35 For each test case, output a single integer — the number of lattice points that have an Euclidean distance $d$ from $(0, 0)$ such that $r \leq d \lt r+1$. 36 37 Example 38 39 Input 40 41 ``` 42 6 43 44 1 45 46 2 47 48 3 49 50 4 51 52 5 53 54 1984 55 ``` 56 57 Output 58 59 ``` 60 8 61 16 62 20 63 24 64 40 65 12504 66 ``` 67 68 Note 69 70 The points for the first three test cases are shown below. 71 72 