e-olymp 97. Числа Белла

Задача

Bell
Число Белла $B_n$ равно количеству разбиений множества из $n$ элементов на произвольное количество непересекающихся непустых подмножеств. Например, $B_3 = 5$, так как существует $5$ возможных разбиений множества $\lbrace a, b, c\rbrace$: $\lbrace\lbrace a\rbrace, \lbrace b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, c\rbrace, \lbrace b\rbrace\rbrace, \lbrace\lbrace a\rbrace, \lbrace b, c\rbrace\rbrace, \lbrace\lbrace a, b, c\rbrace\rbrace$. Дополнительно считаем, что $B_0 = 1$.
Рассмотрим определитель $D_n$:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix}$$
Для заданного простого числа $p$ найти наибольшее целое $k$, для которого $D_n$ делится на $p^k$.

Входные данные

Каждая строка ввода содержит два целых числа $n$ и $p$ ($0\leq\; n,\;p \;\leq\; 10000$). Известно, что $p$ – простое.

Выходные данные

Для каждой пары входных значений $n$ и $p$ в отдельной строке выведите наибольшее целое $k$, для которого $D_n$ делится на $p^k$.

Тесты

Входные данные Выходные данные
1 5
3 2
4 2
4 3
10000 3
0
2
5
2
24962375
18 2
465 1009
9998 9221
548 11
134
0
778
14412
1093 1093
1103 1723
3931 617
4868 6113
9534 71
1
0
10635
0
639989
617 17
42 11
0 5
11295
63
0

Код программы

Решение

Числа Белла обладают интересным свойством:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix} = \prod_{i=1}^n i!$$
Воспользуемся этим свойством для решения данной задачи. Найдём степень числа $p$
в разложении на простые множители. Для этого узнаем степень вхождения этого числа в каждый из факториалов. Суммой полученных значений и будет являться искомое число $k$.

Ссылки

Условие задачи на e-olymp
Решение на ideone
Решение на e-olymp
Число Белла на wikipedia

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *