You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
译自 ROI 2018 Regional. Day1 T2. Квадраты и кубы
数学家们研究了「自然数的平方的分布」与「自然数的立方的分布」之间的关系。
已知非负整数 a,b,k。考虑集合 S={a,a+1,…,b}，该集合的「k 密度」表示的是 T 中元素的个数，其中 T={(x,y)∣ x∈N, y∈N, x2∈S, y3∈S, ∣x2−y3∣≤k}。请求出 S 的 k 密度。
输入格式
输入包含三行，分别为 a,b,k。
输出格式
输出一行，表示答案。
1
30
2
3
提示
样例解释
- x=1,y=1,∣x2−y3∣=∣1−1∣=0;
- x=3,y=2,∣x2−y3∣=∣9−8∣=1;
- x=5,y=3,∣x2−y3∣=∣25−27∣=2.
数据范围
对于所有数据，1≤a≤b≤1018, 0≤k≤1018.
| 子任务编号 |
分值 |
1≤a≤b≤ |
k |
| 1 |
10 |
1000 |
k=0 |
| 2 |
10 |
1018 |
| 3 |
15 |
1000 |
0≤k≤10 |
| 4 |
15 |
106 |
| 5 |
15 |
109 |
| 6 |
15 |
0≤k≤109 |
| 7 |
20 |
1018 |
0≤k≤1018 |
梁泽贤 (liangzexian)