Подразделы

Другие разделы

Дата и время

09/04/2025 14:00:48

Авторизация

Лето 6

A. Метрополитен B. Очень легкая задача C. Шахматная доска D. Интересный треугольник E. Galaxy F. Robot G. Schedule H. Ancestor I. Grid J. Hosting K. BitSort

D. Интересный треугольник

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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

Пример ввода 2

48 3

Пример вывода 2

Источник: РГУ им. И.Канта, осенний командный турнир, 2007