「CMOI R0」Parallel Universe Shifter / Lattices in Circle

ID: 8327

远端评测题

250~4000ms

512MiB

难度: 9

上传者:

标签>

贪心

2005

二分

USACO

Description

求与原点距离不超过 $n(1\leq n\leq 10^{12})$ 的整点个数。

一行一个正整数 $n$ 。

一行一个正整数，即答案。注意它可能大于 $2^{64}$ 。

2827432965

10000000

314159265350589

500000000

785398163397389961

16000000000

804247719318986163169

700000000000

1539380400258998682200449

符合条件的 $5$ 个点是 $(0,0),(1,0),(0,1),(0,-1),(-1,0)$ 。

$\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$