20429번 - Квадраты и кубы 다국어

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

Пусть задано целое неотрицательное число k. Рассмотрим множество натуральных чисел от a до b, включительно. Будем называть k-плотностью этого множества количество пар натуральных чисел x и y, таких, что a ≤ x² ≤ b, a ≤ y³ ≤ b, причем |x² – y³| ≤ k.

Например, 2-плотность множества натуральных чисел от 1 до 30 равна 3, так как подходят следующие пары:

• x = 1, y = 1, |x² – y3| = |1 – 1| = 0;
• x = 3, y = 2, |x² – y3| = |9 – 8| = 1;
• x = 5, y = 3, |x² – y3| = |25 – 27| = 2.

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

Входные данные содержат три строки. Первая строка содержит натуральное число a, вторая строка содержит натуральное число b, третья строка содержит целое неотрицательное число k (1 ≤ a ≤ b ≤ 10¹⁸, 0 ≤ k ≤ 10¹⁸).

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