codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/5fc6e2d468e278c2f3d25f3567124ea0bb45d02b.png)