Учитывая количество тестов 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), представляет количество тестовых случаев. <br>Каждая из следующих T строк содержит целое число N (1 <= N <= 40000, N ^ 4 не будет превышать 64-разрядное целое число). <br>
Этот вопрос находится на Hackerearth в категории рекурсии, но я не могу понять алгоритм в редакционной статье (редакционная ссылка: - https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/practice-problems/algorithm/divide-number-a410603f/editorial/).
В редакционной статье это было решено с использованием дробных единиц, но я не могу понять алгоритм (я предоставил редакционную статью ниже, если вы не можете открыть вышеуказанную ссылку, я не могу понять точки, отмеченные ***). Решение по грубой силе приводит к TLE (Превышен лимит времени). Пожалуйста, предоставьте алгоритм или псевдокод с использованием DFS или обратного отслеживания.
Мой метод грубой силы: - вычислите факторы числа 'n' в O (sqrt (n)) и сохраните их в массиве, затем проследите массив для получения A, B, C, D, используя четыре цикла for. Но для тестовых случаев T (1 <= T <= 40000) он получает TLE. </p>
Редакционное (Если вы не можете открыть вышеуказанную ссылку): -
Рассмотрим уравнение 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 - число Контрольные примеры.