Задача 2. Квадраты и кубы

Автор:Центральная предметно-методическая комиссия   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

В лаборатории теории чисел одного университета изучают связь между распределением квадратов и кубов натуральных чисел.

Пусть задано целое неотрицательное число k. Рассмотрим множество натуральных чисел от a до b, включительно. Будем называть k-плотностью этого множества количество пар натуральных чисел x и y, таких, что a ≤ x2 ≤ b, a ≤ y3 ≤ b, причем |x2 − y3| ≤ k. Например, 2-плотность множества натуральных чисел от 1 до 30 равна 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.

Требуется написать программу, которая по заданным натуральным числам a и b, а также целому неотрицательному числу k, определяет k-плотность множества натуральных чисел от a до b, включительно.

Формат входных данных

Входные данные содержат три строки. Первая строка содержит натуральное число a, вторая строка содержит натуральное число b, третья строка содержит целое неотрицательное число k.

Формат выходных данных

Выходные данные должны содержать одно целое число: искомую k-плотность множества натуральных чисел от a до b, включительно.

Ограничения

1 ≤ a ≤ b ≤ 1018, 0 ≤ k ≤ 1018

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Ограничения Необходимые подзадачи Информация о проверке
a, bk
1101 ≤ a ≤ b ≤ 1000k = 0полная
2101 ≤ a ≤ b ≤ 1018k = 01полная
3151 ≤ a ≤ b ≤ 10000 ≤ k ≤ 101полная
4151 ≤ a ≤ b ≤ 1060 ≤ k ≤ 101, 3полная
5151 ≤ a ≤ b ≤ 1090 ≤ k ≤ 101, 3, 4полная
6151 ≤ a ≤ b ≤ 1090 ≤ k ≤ 1091, 3, 4, 5полная
7201 ≤ a ≤ b ≤ 10180 ≤ k ≤ 10181 − 6полная

Примеры тестов

Стандартный вход Стандартный выход
1
1
30
2
3

0.097s 0.017s 13