Background

The original "[USACO05FEB] Aggressive Cows G" can be found at P1824.

$$\text{Answer}=\pi n^2+\mathrm O(n^{\frac{517}{824}}).$$

$\small\color{white}/35^{\text{th}}\text{Problem by AtC}.$

Problem Description

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

Input Format

One line with one positive integer $n$.

Output Format

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

1

5

2

13

5

81

19

1129

100

31417

30000

2827432965

10000000

314159265350589

500000000

785398163397389961

16000000000

804247719318986163169

700000000000

1539380400258998682200449

Hint

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$		$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}$		$40$

Translated by ChatGPT 5