Не могу понять, как эту задачу можно решить без "тупого" перебора чисел от НОК/данное число, до самого НОК. Число, которое нужно найти, должно быть минимальным подходящим к данным.
Можно выразить искомое число через НОД(неизвестный)*НОК/данное_число, но тогда не понятно, как обратно идти от НОД к числу. Также можно разложить НОК и дынное число на простые множители, по ним искать третье (опорная точка -- произведение чисел, которые есть в разложении НОК но нет в разложении данного нам числа), но тут как раз перебор с проверкой (правда, чуть поменьше). Второй вариант сложнее при очень больших числах.
Перебором нельзя т.к. числа будут огромные. Написать код не прошу, просто интересна сама суть решения, правильно ли я вообще думаю.
Ответ
Раскладываем на простые множители НОК. Получаем список множитель-кратность (например, при разложении 12 будет два множителя - 2 с кратностью 2 и 3 с кратностью 1). Назовём его список1. Раскладываем на простые множители имеющееся число (назовём его список2). Далее обрабатываем оба списка, создавая список3.
Если некий множитель отсутствует в список1, но имеется в список2, задача нерешаема.
Если кратность множителя в список1 меньше его кратности в список2, задача нерешаема.
Если некий множитель имеется в список1, но отсутствует в список2, он помещается в список3 с той же кратностью, что и в список1
Если кратность множителя в список1 больше его кратности в список2, он помещается в список3 с той же кратностью, что и в список1
Если некий множитель имеется в список1 и список2 с одинаковой кратностью, он помещается в список3 с кратностью 0 (ноль).
Перемножая множители из список3 с учётом кратности, получаем минимальное решение. Остальные решения получаем увеличением кратности одного или нескольких множителей в список3, но не превышая их кратности в список1
Всё.
Комментариев нет:
Отправить комментарий