P1676 "CMOI R0" Parallel Universe Shifter / Lattices in Circle

The original "[USACO05FEB] Aggressive Cows G" can be found at [P1824](https://www.luogu.com.cn/problem/P1824). $$\text{Answer}=\pi n^2+\mathrm O(n^{\frac{517}{824}}).$$  $\small\color{white}/35^{\text{th}}\text{Problem by AtC}.$

Find the number of integer lattice points whose distance to the origin is at most $n$ $(1\leq n\leq 10^{12})$.

One line with one positive integer $n$.

One line with one positive integer, the answer. Note that it may be greater than $2^{64}$.

### Explanation for Sample $1$ The $5$ points that satisfy the condition are $(0,0),(1,0),(0,1),(0,-1),(-1,0)$. ### Constraints |$\text{Subtask}$|$\text{Special Constraints}$|$\text{Time Limit}$|$\text{Points}$| | :----------: | :----------: | :----------: | :----------: | |$1$|$1\leq n\leq 2\times 10^3$|$0.25\text s$|$1$| |$2$|$10^4\leq n\leq 10^7$|$1\text s$|$4$| |$3$|$10^8\leq n\leq 10^9$|$1\text s$|$10$| |$4$|$10^9\leq n\leq 10^{10}$|$3\text s$|$15$| |$5$|$10^{10}\leq n\leq 10^{11}$|$4\text s$|$30$| |$6$|$10^{11}\leq n\leq 10^{12}$|$4\text s$|$40$| Translated by ChatGPT 5