report VI VI EN
Register | Login
  • HOME
  • PROBLEMSET
  • ROADMAP
  • COMPETITION
  • TOPIC
  • RANKING
  • GUIDE
  • MASHUP
  • ABOUT
  • CONTACT
  • Problem
  • Submit
  • Results
Square root sum - FlandreOJ: Flandre Online Judge

Square root sum

Time limit: 1000 ms
Memory limit: 256 MB
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 (2) Solution