\begin{proposal}{Наименьшее общее кратное}{lcm.in}{lcm.out}{}

\Author                  
Нияз Нигматуллин

\ProblemIdea
Дано число $N$ и число $k$, нужно определить количество наборов $a_1$, $a_2$, $\ldots$, $a_k$, такие что $lcm(a_1$, $a_2$, $\ldots$,
$a_k) = N$

\SolutionIdea

Динамика.
$dp[i][j][t]$~--- количество наборов из $i$ элементов, таких что $j$ подмножество всех простых делителей $N$ и lcm набранных чисел
делится на произведение всех простых из подмножества, где каждое в степени такой же, что и в $N$, мы уже поюзали все числа
не более $t$.

Было придумано более простое решение. $dp[i][j][k]$~--- кол-во наборов из $i$ элементов, таких, что мы поиспользовали делители
не больше $j$, и набрали LCM равный $k$.

\ProblemVariations

\ProblemComplexity
Идея~--- (M/H). Реализация~--- (H).

\WrongSolutions

\end{proposal}
                                       