eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Аликвотные дроби

Аликвотные дроби

В древнем Египте были дроби только с числителем, равным единице, дроби вида 1/n, так называемые аликвотные дроби и еще была дробь 2/3. Дроби с числителем, отличным от единицы записывали как сумму аликвотных дробей например: 2/5 = 1/5 + 1/5,2/7 = 1/4 + 1/28.

Задана некоторые натуральные P, Q, A и N. Сколько существует способов представить дробь P/Q в виде суммы аликвотных дробей, так, чтобы количество слагаемых не превышало N, а произведение знаменателей A. Перестановки слагаемых считаются одним способом.

Например, ту же выше упомянутую уникальную египетскую дробь 2/3 при условии, что заданные P, Q, A, N равны соответственно 2, 3, 120, 3 можно представить 4-мя следующими способами при помощи аликвотных дробей:

prb261

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

Каждый тест состоит из нескольких тестовых случаев, количество которых не превышает 200. В каждой входной строке через пробел задано четыре числа P, Q, A и N.

0 <= P, Q <= 800, 0 <= A <= 12000, 0 <= N <= 7.

Последних четыре числа в тесте 0, 0, 0, 0 являются признаком окончания тестовых данных.

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

Для каждого тестового случая в отдельной строке вывести ответ на поставленную задачу.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
2 3 120 3
2 3 300 3
2 4 54 2
0 0 0 0
Выходные данные #1
4
7
3