НачалоПодразделы
| 975. Метрополитен |
| 976. Очень легкая задача |
| 977. Шахматная доска |
| 978. Интересный треугольник |
| 979. Galaxy |
| 980. Robot |
| 981. Schedule |
| 982. Ancestor |
| 983. Grid |
| 984. Hosting |
| 985. BitSort |
Дата и время
24/11/2024 12:12:47
Лето 6
A. Метрополитен B. Очень легкая задача C. Шахматная доска D. Интересный треугольник E. Galaxy F. Robot G. Schedule H. Ancestor I. Grid J. Hosting K. BitSort
D. Интересный треугольник
Вывод формулыОлимпиадные задачи на русском языке
| 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
