Задача
Число Белла $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 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
import java.util.Scanner; public class Main { public static void main (String[] args) { Scanner scanner = new Scanner(System.in); int n, p; while(scanner.hasNextInt()) { n = scanner.nextInt(); p = scanner.nextInt(); int k = 0; for (int i = 1; i 0) { fact /= p; k += fact; } } System.out.println(k); } } } |
Решение
Числа Белла обладают интересным свойством:
$$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