ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1057. Количество степеней

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Напишите программу для определения количества целых чисел, лежащих на отрезке [X; Y] и представляющих собой сумму ровно K различных степеней целого числа B с целыми показателями.
Пример. Пусть X = 15, Y = 20, K = 2, B = 2. В данном примере три целых числа представляют собой сумму ровно двух целых степеней числа 2:
17 = 24 + 20,
18 = 24 + 21,
20 = 24 + 22.

Исходные данные

Первая строка содержит целые числа X и Y (1 ≤ X ≤ Y ≤ 231 − 1). Следующие две строки содержат целые числа K и B (1 ≤ K ≤ 20; 2 ≤ B ≤ 10).

Результат

Выведите количество целых чисел, лежащих между X и Y, которые представляют собой сумму ровно K различных степеней целого числа B с целыми показателями.

Пример

исходные данныерезультат
15 20
2
2
3
Источник задачи: Rybinsk State Avia Academy