Məsələlər
Разделение на доли
Разделение на доли
A fraction whose numerator is \textbf{1} and whose denominator is a positive integer is called a unit fraction. A representation of a positive rational number \textbf{p/q} as the sum of finitely many unit fractions is called a partition of \textbf{p/q} into unit fractions. For example, \textbf{1/2 + 1/6} is a partition of \textbf{2/3} into unit fractions. The difference in the order of addition is disregarded. For example, we do not distinguish \textbf{1/6 + 1/2} from \textbf{1/2 + 1/6}.
For given four positive integers \textbf{p}, \textbf{q}, \textbf{a}, and \textbf{n}, count the number of partitions of \textbf{p/q} into unit fractions satisfying the following two conditions.
\begin{itemize}
\item The partition is the sum of at most \textbf{n} many unit fractions.
\item The product of the denominators of the unit fractions in the partition is less than or equal to \textbf{a}.
\end{itemize}
For example, if \textbf{(p,q,a,n) = (2,3,120,3)}, you should report \textbf{4} since
\includegraphics{https://static.e-olymp.com/content/2e/2e1fbb3638824ffb3ae12476bdfab84648f7a3cc.jpg}
enumerates all of the valid partitions.
\InputFile
Содержит не более \textbf{200} тестов. Каждый тест представляет собой строку из четырех положительных целых чисел \textbf{p}, \textbf{q}, \textbf{a }и \textbf{n}, причем \textbf{p}, \textbf{q} ≤ \textbf{800}, \textbf{a} ≤ \textbf{12000} и \textbf{n} ≤ \textbf{7}. Все числа разделены пробелами.
Последняя строка содержит четыре нуля и не обрабатывается.
\OutputFile
Для каждого теста вывести в отдельной строке ответ на задачу. Каждое целое число должно соответствовать для заданного набора чисел \textbf{p}, \textbf{q}, \textbf{a}, \textbf{n }количеству представлений дроби \textbf{p}/\textbf{q }не более чем \textbf{n }слагаемыми, произведение знаменателей в которых не превышает \textbf{a}.
Giriş verilənləri #1
2 3 120 3 2 3 300 3 2 3 299 3 2 3 12 3 2 3 12000 7 54 795 12000 7 2 3 300 1 2 1 200 5 2 4 54 2 0 0 0 0
Çıxış verilənləri #1
4 7 6 2 42 1 0 9 3