#3024. 「ROIR 2018 Day1」平方与立方

内存限制:512 MiB 时间限制:200 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

译自 ROI 2018 Regional. Day1 T2. Квадраты и кубы

数学家们研究了「自然数的平方的分布」与「自然数的立方的分布」之间的关系。

已知非负整数 a,b,k 。考虑集合 S=\{a,a+1,\ldots,b\} ,该集合的「 k 密度」表示的是 T 中元素的个数,其中 T=\{(x,y)| x\in\mathbb{N}, y\in\mathbb{N}, x^2\in S, y^3\in S, |x^2 - y^3| ≤ k\} 。请求出 S k 密度。

样例

样例输入

1
30
2

样例输出

3

样例说明

  • x = 1, y = 1, |x^2 - y^3| = |1 - 1| = 0 ;
  • x = 3, y = 2, |x^2 - y^3| = |9 - 8| = 1 ;
  • x = 5, y = 3, |x^2 - y^3| = |25 - 27| = 2 .

数据范围与提示

对于所有数据, 1 ≤ a ≤ b ≤ 10^{18}, 0 ≤ k ≤ 10^{18} .

子任务编号 分值 1 ≤ a ≤ b ≤ k
1 10 1000 k = 0
2  10  10^{18}
3 15 1000 0 ≤ k ≤ 10
4  15  10^6
5 15 10^9
6  15  0 ≤ k ≤ 10^9
7 20 10^{18} 0 ≤ k ≤ 10^{18}