Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
978. Интересный треугольник
Вывод формулыОлимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание ( 6D) |
| 14/07/2008 | Лето 2008 - 6 (D) |
Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Как известно, любимая задача программеров всего мира формулируется так: найти сумму элементов `N`-ой строки треугольника Паскаля. Известны многочисленные варианты этой задачи. Так в одном из наших турниров была предложена исключительно красивая задача о нахождении суммы биномиальных коэффициентов `C(N,1)+…+C(N,N)`. Когда-нибудь жюри ещё вернётся к этой прекрасной задаче, но сегодня мы рассмотрим другие свойства треугольника Паскаля. Этот интересный математический объект обладает совершенно фантастическими свойствами! Например, `N`-я строка содержит ровно `N+1` элемент!!! Наука до сих пор не смогла объяснить этот поразительный факт! Но сейчас давайте решим более простой вопрос – сколько чисел в `N`-ой строке треугольника Паскаля не делится на заданное простое число `P`?
Ввод
Во входном файле записано число `N` (`0\ ≤\ N\ ≤\ 1\ 000\ 000\ 000`) и простое число `P` (`P\ <\ 1000`).
Вывод
Запишите в выходной файл количество чисел в `N`-ой строке треугольника Паскаля, не делящихся на `P`.
Пример ввода 1
4 3
Пример вывода 1
4
Пример ввода 2
48 3
Пример вывода 2
12
