Учитывая количество тестовых случаев T и целое число N, вам нужно найти четыре целых числа A,B,C,D , чтобы все они были факторами N(A|N,B|N,C|N,D|N ) и N=A+B+C+D. Цель состоит в том, чтобы максимизировать A * B * C * D. Если невозможно найти такие четыре фактора, просто верните -1.
Формат ввода для задачи:
Первая строка содержит целое число T(1 ‹=T‹=40000), представляет количество тестов.
Каждая из следующих T строк содержит целое число N (1‹=N‹=40000, N^4 не будет превышать 64-битного целого числа).
Этот вопрос находится на Hackerearth в категории рекурсии, но я не могу понять алгоритм в редакционной статье (редакционная ссылка: - https://www.hackerearth.com/practice/basic-programming/recursion/рекурсия-и-возврат/проблемы-практики/алгоритм/номер-разделения-a410603f/editorial/).
В редакционной статье это было решено с использованием единичных дробей, но я не могу понять алгоритм (я предоставил редакционную статью ниже, если вы не можете открыть приведенную выше ссылку, я не могу понять пункты, отмеченные ***). Решение грубой силы приводит к TLE (превышено ограничение по времени). Предоставьте алгоритм или псевдокод с использованием DFS или поиска с возвратом.
Мой подход грубой силы: вычислить коэффициенты числа 'n' в O (sqrt (n)) и сохранить их в массиве, а затем пройти по массиву, чтобы получить A, B, C, D, используя четыре цикла for. Но для тестов T(1‹=T‹=40000) он получает TLE.
От редакции(Если вы не можете открыть вышеуказанную ссылку):-
Рассмотрим уравнение N = A+B+C+D , если разделить уравнение на N , получим 1 = 1/A' + 1/B' + 1/C' + 1/D' , здесь A',B ',C',D' являются целыми числами, потому что A,B,C,D являются множителями числа N.
Таким образом, исходная задача равна делению 1 на четыре единицы измерения.
Мы можем перечислить единичные дроби от больших к малым.
*** Если нам нужно разделить X на Y единичных дробей, а последней единичной дробью является 1/Z, мы можем перечислить единичные дроби между 1/Z и X/Y (поскольку мы перечисляем наибольшую оставшуюся дробь) и рекурсивно решать.
*** Найдя все решения уравнения 1 = 1/A' + 1/B' + 1/C' + 1/D' (около 20 решений, если числа упорядочены), мы можем перечислить их в каждом наборе входных данных. Если A', B', C', D' являются факторами N, мы можем использовать это решение для обновления ответа.
Временная сложность: O(T), где T — количество тестовых случаев.
