Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2296. Задача
Элементы теории чисел, диофантовы уравненияМодулярная арифметика
Олимпиадные задачи на русском языке
| 02/10/2016 | Личное первенство по спортивному программированию (E) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Мистер Гаррисон задал ученикам следующую задачу:
"Найти максимальное подмножество чисел из чисел от 1 до `N`, в котором нет чисел
ровно в `p` раз больше какого-либо другого числа из этого подмножества" и указал каждому
школьнику значения `N` и `p` индивидуально.
Напишите программу, которая поможет мистеру Гаррисону проверить ответы учеников.
Первая строка ввода содержит два целых числа `N` (`1\ ≤\ N\ ≤\ 10^9`) и `p` (`2\ ≤\ p\ <\ 100`, `p` – простое число).
Вывести два целых числа – максимальное количество элементов в искомом подмножестве и
количество вариантов таких максимальных подмножеств по модулю `10^9+7`.
Пример ввода
8 2
Пример вывода
5 6
Пояснение к примеру: существует 6 максимальных подмножеств из 5 значений
{1,3,4,5,7}, {1,4,5,6,7}, {1,3,5,7,8}, {1,5,6,7,8}, {2,3,5,7,8} и {2,5,6,7,8}.
