Start 2024-10-04 19:27:29

1005CSP模拟赛

End 2024-11-05 12:00:00
Contest is over.
Now 2025-10-14 01:32:42

C. 区间开方和

Description

输入 l,r,输出 l\sim r 的每个数的算数平方根下取整之和,即:

\sum_{i=l}^r \lfloor\sqrt{i}\rfloor

Input

两个整数 l,r

Output

输出一个整数,即算数平方根之和。

Examples

Input

4 9

Output

13

Hint

样例解释:4\sim 9 的算术平方根下取整分别为 2,2,2,2,2,3,和为 13。大样例就不给了。

数据规模与约定

对于 100\% 的数据,0 \le l\le r \le 10^{14}

  • 子任务 1(40 分):保证 r\le 10^7
  • 子任务 2(30 分):保证 l=r
  • 子任务 3(20 分):保证 r-l\le 10^7
  • 子任务 4(10 分):没有特殊限制。

Submit

Login

Signup
Time Limit 1 second
Memory Limit 128 MB
Submit