Квадраты и кубы
В лаборатории теории чисел одного университета изучают связь между распределением квадратов и кубов натуральных чисел.
Пусть задано целое неотрицательное число k . Рассмотрим множество натуральных чисел от a до b , включительно. Будем называть k -плотностью этого множества количество пар натуральных чисел x и y , таких, что a ≤ x 2 ≤ b , a ≤ y 3 ≤ b , причем | x 2 – y 3 | ≤ k .
Например, 2 -плотность множества натуральных чисел от 1 до 30 равна 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 .
Требуется написать программу, которая по заданным натуральным числам a и b , а также целому неотрицательному числу k , определяет k -плотность множества натуральных чисел от a до b , включительно.
Входные данные содержат три строки. Первая строка содержит натуральное число a , вторая строка содержит натуральное число b , третья строка содержит целое неотрицательное число k ( 1 ≤ a ≤ b ≤ 10 18 , 0 ≤ k ≤ 10 18 ).
Выходные данные должны содержать одно целое число: искомую k -плотность множества натуральных чисел от a до b , включительно.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
1 30 2
3