Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 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,b | k | ||||
1 | 10 | 1≤a≤b≤1000 | k=0 | полная | |
2 | 10 | 1≤a≤b≤1018 | k=0 | 1 | полная |
3 | 15 | 1≤a≤b≤1000 | 0≤k≤10 | 1 | полная |
4 | 15 | 1≤a≤b≤106 | 0≤k≤10 | 1,3 | полная |
5 | 15 | 1≤a≤b≤109 | 0≤k≤10 | 1,3,4 | полная |
6 | 15 | 1≤a≤b≤109 | 0≤k≤109 | 1,3,4,5 | полная |
7 | 20 | 1≤a≤b≤1018 | 0≤k≤1018 | 1−6 | полная |
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|