Square root sum - MarisaOJ: Marisa Online Judge

For two non-negative integers

$a, b$ , calculate the sum of the floor of the square root for all integers

$i$ with

$a \leq i \leq b$ . In other words, calculate:

$\sum_{i=a}^b \lfloor \sqrt{i} \rfloor$ . Here,

$\lfloor a \rfloor$ denotes the greatest integer not greater than

$a$ . ### Input - Contains a single line with two positive integers

$a, b$ . ### Output - Print the result of the calculation. ### Constraint -

$1 \le a \le b \le 10^{12}$ . ### Sample Test **Input 1**

$3 10$

**Output 1**

$17$

**Explanation**

$\lfloor \sqrt{3} \rfloor + \lfloor \sqrt{4} \rfloor + \lfloor \sqrt{5} \rfloor + \lfloor \sqrt{6} \rfloor + \lfloor \sqrt{7} \rfloor + \lfloor \sqrt{8} \rfloor + \lfloor \sqrt{9} \rfloor + \lfloor \sqrt{10} \rfloor$

$=1+2+2+2+2+2+3+3=17$ **Input 2**

$14 29$

**Output 2**

$67$

Basic number theory
	Prime number 2
	Sieve of Eratosthenes
	Segmented sieve
	Prime factors
	Maximum GCD
	Divisors counting
	Largest common divisor
	Nearest Element
	Divisors counting 2
	GCD and LCM
	GGCD
	Square root sum
	Square number
	Sum sum sum

Topic

Math

Rating

1200

Solution (1)

Solution